[solved.ac 실버2] 3187_양치기 꿍 (파이썬, BFS)

제한 사항

 

문제

양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다.

하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다.

꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산할 수 있겠는가?

단, 울타리로 막히지 않은 영역에는 양과 늑대가 없으며 양과 늑대는 대각선으로 이동할 수 없다.

입력

입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다.

다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다.

출력

살아남게 되는 양과 늑대의 수를 각각 순서대로 출력한다.

예제

 

---

나의 풀이

인접한 곳을 방문하며 하나의 그룹으로 처리해야 할 때 BFS를 주로 사용한다.

이 문제에서 3 ≤ R, C ≤ 250 로 주어졌기 때문에 최악의 상황에 250 * 250 = 62500 번 순회하므로 시간 안에 풀이할 수 있다.

 

전역 변수

from collections import deque

r, c = map(int, input().split())
arr = [list(input()) for _ in range(r)]
visited = [[False] * c for _ in range(r)]
d = [(-1, 0), (0, -1), (1, 0), (0, 1)] # ↑ ← ↓ →
v, k = 0, 0 # v: 늑대, k: 양

BFS를 수행하기 위해 Queue 처럼 동작할 수 있는 collections.deque을 import 했고, 사용자에게 r, c, arr를 입력 받는다.

방문 체크를 하기 위해 r * c 크기의 visited 리스트를 만들었고, 인접한 방향(상, 하, 좌, 우)을 이동하기 위한 d 리스트를 만들었다.

최종적으로 남아있을 늑대와 양의 수를 저장하기 위한 v, k를 각각 0으로 초기화했다.

 

BFS

def bfs(a, b):
    global r, c, d, v, k
    sheep, wolf = 0, 0

    queue = deque([(a, b)])
    visited[a][b] = True
    if arr[a][b] == 'v': wolf += 1 # 늑대
    if arr[a][b] == 'k': sheep += 1 # 양

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + d[i][0], y + d[i][1]
            if nx in range(r) and ny in range(c) and \
                arr[nx][ny] != '#' and not visited[nx][ny]:
                visited[nx][ny] = True
                if arr[nx][ny] == 'v': wolf += 1 # 늑대
                if arr[nx][ny] == 'k': sheep += 1 # 양
                queue.append((nx, ny))
    if wolf >= sheep: v += wolf
    else: k += sheep

나중에 bfs 함수를 호출하는 부분을 보면 알겠지만 한 번도 방문하지 않았던 '울타리'일 때만 bfs 함수에 진입한다. 

그리고 bfs 함수 수행이 완료되면 현재 울타리 내부를 모두 탐색이 완료된다. 즉, 여기서 양(sheep)과 늑대의 수(wolf)를 세고 양이 늑대보다 많다면 전체 양(전역 변수 k)에 양(sheep)의 수를 더하고, 그렇지 않으면 전체 늑대(v)에 늑대(wolf)의 수를 더한다.

코드에 대한 자세한 설명은 BFS에 대해 알고 있다면 쉽게 알 수 있는 부분이라 생략한다.

수행

def solution():
    global r, c, arr

    for x in range(r):
        for y in range(c):
            if arr[x][y] != '#' and not visited[x][y]:
                bfs(x, y)

    print(k, v)

모든 위치를 순회하며 해당 위치가 울타리(#)가 아니면서 아직 방문하지 않았을 때만 bfs 함수를 수행한다.

bfs 함수가 수행되면 울타리 내부는 모두 순회 가능하기에 bfs 함수가 호출될 때는 항상 새로운 울타리 공간일 때다.

주어진 모든 위치가 순회되었다면 전역 변수 k, v에는 각각 양과 늑대의 수가 저장되어 있게 된다. 이를 출력해준다.

 

전체 코드

from collections import deque

r, c = map(int, input().split())
arr = [list(input()) for _ in range(r)]
visited = [[False] * c for _ in range(r)]
d = [(-1, 0), (0, -1), (1, 0), (0, 1)] # ↑ ← ↓ →
v, k = 0, 0 # v: 늑대, k: 양

def bfs(a, b):
    global r, c, d, v, k
    sheep, wolf = 0, 0

    queue = deque([(a, b)])
    visited[a][b] = True
    if arr[a][b] == 'v': wolf += 1 # 늑대
    if arr[a][b] == 'k': sheep += 1 # 양

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + d[i][0], y + d[i][1]
            if nx in range(r) and ny in range(c) and \
                arr[nx][ny] != '#' and not visited[nx][ny]:
                visited[nx][ny] = True
                if arr[nx][ny] == 'v': wolf += 1 # 늑대
                if arr[nx][ny] == 'k': sheep += 1 # 양
                queue.append((nx, ny))
    if wolf >= sheep: v += wolf
    else: k += sheep

def solution():
    global r, c, arr

    for x in range(r):
        for y in range(c):
            if arr[x][y] != '#' and not visited[x][y]:
                bfs(x, y)

    print(k, v)

solution()

 

채점 결과