[실버 1] 백준 3184 - 양 (파이썬)

https://www.acmicpc.net/problem/3184

풀이

• 울타리로 막혀 있는 공간 안에 양과 늑대가 있다.
• 한 영역에서 양의 수가 늑대보다 많으면 양이 살아남고, 늑대가 더 많거나 같으면 늑대가 살아남음
• 최종적으로 살아남은 양과 늑대의 수를 구하는 문제

R, C = map(int, input().split())
B = [input() for _ in range(R)]

R, C는 행, 열 크기를 나타내며, B는 농장의 상태를 저장한 2차원 리스트이다.

대표적인 BFS 문제이다. 해당 문제는 visit 배열을 사용해서 풀이가 가능하다.

visit = [[False] * C for _ in range(R)]
queue = deque()

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

final_o, final_v = 0, 0

visit은 이미 방문한 칸을 표시하는 배열이며, queue는 BFS 탐색에 사용할 큐이다.

dr, dc는 상하좌우 이동을 위한 방향 벡터이며, final_o, final_v는 최종적으로 살아남은 양과 늑대의 수를 나타낸다.

for i in range(R):
    for j in range(C):
        if B[i][j] != '#' and not visit[i][j]:

울타리가 아니고, 아밎 ㄱ방문하지 않은 칸이라면, 새로운 하나의 영역을 발견한 것이다. 이때 BFS를 시작한다.

queue.append((i, j))
visit[i][j] = True

o_count = 1 if B[i][j] == 'o' else 0
v_count = 1 if B[i][j] == 'v' else 0

(i, j)를 큐에 넣고 방문 처리를 시작하고, 시작 지점이 양이면 o_count += 1, 늑대면 v_count += 1을 처리한다.

while len(queue) != 0:
    r, c = queue.popleft()

본격적으로 BFS를 진행한다. 해당 코드는 큐에서 하나 꺼내서 4방향으로 탐색을 진행한다.

for k in range(4):
    nr, nc = r + dr[k], c + dc[k]

    if nr < 0 or R <= nr or nc < 0 or C <= nc:
        continue
    if B[nr][nc] == '#':
        continue
    if not visit[nr][nc]:
        queue.append((nr, nc))
        visit[nr][nc] = True

        if B[nr][nc] == 'o':
            o_count += 1
        if B[nr][nc] == 'v':
            v_count += 1

범위를 벗어나거나, 울타리면 건너뛴다. 새로운 양이나 늑대를 발견하면 각각 수를 세어준다.

if o_count > v_count:
    final_o += o_count
else:
    final_v += v_count

하나의 영역 탐색 완료 후 양이 더 많으면 양만 살아남아 final_o에 추가하고, 늑대가 많거나 같으면 늑대만 살아남아 final_y에 추가한다.

코드

# 백준 3184 - 양
# 분류 : BFS

from collections import deque

R, C = map(int, input().split())
B = [input() for _ in range(R)]

visit = [[False] * C for _ in range(R)]
queue = deque()

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

final_o, final_v = 0, 0
for i in range(R) :
    for j in range(C) :
        if B[i][j] != '#' and not visit[i][j] :
            queue.append((i, j))
            visit[i][j] = True

            o_count = 1 if B[i][j] == 'o' else 0
            v_count = 1 if B[i][j] == 'v' else 0

            while len(queue) != 0 :
                r, c = queue.popleft()

                for k in range(4) :
                    nr, nc = r + dr[k], c + dc[k]

                    if nr < 0 or R <= nr or nc < 0 or C <= nc :
                        continue
                    if B[nr][nc] == '#' :
                        continue
                    if not visit[nr][nc] :
                        queue.append((nr, nc))
                        visit[nr][nc] = True

                        if B[nr][nc] == 'o' :
                            o_count += 1
                        if B[nr][nc] == 'v' :
                            v_count += 1
            
            if o_count > v_count :
                final_o += o_count
            else :
                final_v += v_count

print(final_o, final_v)