백준 3184: 양 Python

 

1. 메모리 초과

이번 문제는 이해하기는 쉬운데, 구현 도중 시간 초과 혹은 메모리 초과 조건이 까다로웠다.

아래처럼 했을 때 메모리 초과가 나왔는데, 각 셀에 대해 bfs를 돌릴 때 조건이 visited[i][j] = 1이면서 arr[i][j] != '#'일 때로 설정해뒀기 때문에 그런 것 같다.

# 메모리 초과
from collections import deque
import sys
input = sys.stdin.readline


def bfs(si, sj):
    global sheep, wolf
    q = deque()
    q.append((si, sj))
    n_sheep, n_wolf = 0, 0

    while q:
        si, sj = q.popleft()

        if not visited[si][sj] and arr[si][sj] == 'o':
            n_sheep += 1
        if not visited[si][sj] and arr[si][sj] == 'v':
            n_wolf += 1
        visited[si][sj] = 1

        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = si+di, sj+dj
            if 0 <= ni < R and 0 <= nj < C:
                if not visited[ni][nj] and arr[ni][nj] != '#':
                    q.append((ni, nj))
    if n_sheep > n_wolf:
        sheep += n_sheep
    else:
        wolf += n_wolf


R, C = map(int, input().split())    # R: 행, C: 열
arr = [list(input().rstrip()) for _ in range(R)]
sheep = 0   # 최종 양 수
wolf = 0    # 최종 늑대 수
visited = [[0] * C for _ in range(R)]   # 방문 체크
for i in range(R):
    for j in range(C):
        if not visited[i][j] and arr[i][j] != '#':
            bfs(i, j)
print(sheep, wolf)

 

2. 시간 초과

위에서 언급한 부분을 고쳤는데도 시간초과가 났다.

이유는 bfs 함수 안에 있는데, while q를 할 때마다 if not visited and arr[si][sj] 문을 계속 체크해야 하기 때문에 그런 것 같다.

# 시간초과
from collections import deque
import sys
input = sys.stdin.readline


def bfs(si, sj):
    global sheep, wolf
    q = deque()
    q.append((si, sj))
    n_sheep, n_wolf = 0, 0

    while q:
        si, sj = q.popleft()

        if not visited[si][sj] and arr[si][sj] == 'o':
            n_sheep += 1
        if not visited[si][sj] and arr[si][sj] == 'v':
            n_wolf += 1
        visited[si][sj] = 1

        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = si+di, sj+dj
            if 0 <= ni < R and 0 <= nj < C:
                if not visited[ni][nj] and arr[ni][nj] != '#':
                    q.append((ni, nj))
    if n_sheep > n_wolf:
        sheep += n_sheep
    else:
        wolf += n_wolf


R, C = map(int, input().split())    # R: 행, C: 열
arr = [list(input().rstrip()) for _ in range(R)]
sheep = 0   # 최종 양 수
wolf = 0    # 최종 늑대 수
visited = [[0] * C for _ in range(R)]   # 방문 체크
for i in range(R):
    for j in range(C):
        if not visited[i][j] and (arr[i][j] == 'o' or arr[i][j] == 'v'):
            bfs(i, j)
print(sheep, wolf)

 

3. 정답 코드

bfs를 처음 돌릴 때도 양과 늑대의 수를 세야 하고, while문 안에서 4방향 탐색을 할 때도 양과 늑대의 수를 세야 하기 때문에 아래와 같이 코드를 수정했고, 통과했다.

# 정답 코드
from collections import deque
import sys
input = sys.stdin.readline


def bfs(si, sj):
    global sheep, wolf
    q = deque()
    q.append((si, sj))
    n_sheep, n_wolf = 0, 0
    visited[si][sj] = 1
    if arr[si][sj] == 'o':
        n_sheep += 1
    elif arr[si][sj] == 'v':
        n_wolf += 1

    while q:
        si, sj = q.popleft()
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = si+di, sj+dj
            if 0 <= ni < R and 0 <= nj < C and not visited[ni][nj] and arr[ni][nj] != '#':
                q.append((ni, nj))
                visited[ni][nj] = 1
                if arr[ni][nj] == 'o':
                    n_sheep += 1
                elif arr[ni][nj] == 'v':
                    n_wolf += 1
    if n_sheep > n_wolf:
        sheep += n_sheep
    else:
        wolf += n_wolf


R, C = map(int, input().split())    # R: 행, C: 열
arr = [list(input().rstrip()) for _ in range(R)]
sheep = 0   # 최종 양 수
wolf = 0    # 최종 늑대 수
visited = [[0] * C for _ in range(R)]   # 방문 체크
for i in range(R):
    for j in range(C):
        if not visited[i][j] and (arr[i][j] == 'o' or arr[i][j] == 'v'):
            bfs(i, j)
print(sheep, wolf)