👩‍🎓공부 - 2024.01.10 오늘의 백준 문제풀이

3184번 - 양

다시 BFS 문제입니다!

빈공간 / 울타리 / 양 / 늑대로 이루어진 그래프가 주어졌을 때 날이 밝은 후 최종적으로 살아남는 생물과 그 생물의 마릿수를 출력하면 되는 문제입니다.

울타리로 가두어진 공간을 '한 공간'이라고 규정하며, 한 공간 내 양의 수가 늑대보다 많을 경우 양이 그 공간 내 늑대를 쫓아내고, 그렇지 않을 경우 (늑대와 양의 수가 비등하거나 늑대의 수가 더 많은 경우)에는 늑대가 그 공간 내의 양을 모두 잡아먹습니다.

...#..
.##v#.
#v.#.#
#.o#.#
.###.#
...###

이렇게 생긴 테스트케이스가 있다면 1번 공간엔 늑대 한마리가 가둬져 있으니까 늑대 + 1, 2번 공간엔 늑대 하나와 양 하나가 갇혀있으니까 늑대가 양을 잡아먹어서 늑대 + 1, 최종적으로 늑대 2마리가 삽니다.

이제 코드로 들어가봅시다.

R,C = map(int,input().split())
field = []
sheep_ans = 0
wolf_ans = 0
visited = [[0]*C for _ in range(R)]
que = deque()
for _ in range(R):
    a = list(input())
    field.append(a)

먼저 그래프의 크기와 최종적으로 양과 늑대의 마릿수를 표현해줄 변수, 그리고 bfs를 사용하기 위한 que와 백트래킹으로 방문 여부를 표시해줄 visited 등을 선언하겠습니다.

for i in range(R):
    for j in range(C):
        if field[i][j] == 'v' or field[i][j] == 'o':
            bfs(i,j)

그리고 그래프를 하나씩 돌며 양이나 늑대가 나오는 순간부터 탐색을 시작하겠습니다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]

BFS 사용을 위해 deque와 상하좌우 선언을 실시하고

def bfs(x,y):
    que.append([x,y])
    global sheep_ans,wolf_ans
    wolf = 0
    sheep = 0
    visited[x][y] = 1
    if field[x][y] == 'o':
        sheep += 1
    else:
        wolf += 1

본격적으로 BFS 함수 작성을 시작해보겠습니다.

.#.
#v#
.#.

일단 위와같이 늑대 또는 양이 혼자서 갇혀있는 상황이 발생 할 수 있으므로 맨 처음에 받은 인덱스는 방문 처리를 하고 해당 인덱스가 양인지 늑대인지 판단해서 늑대의 지역변수 or 양의 지역변수 + 1을 해주도록 하겠습니다.

    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=R or ny>=C:
                continue

다음으로 BFS 탐색의 기본적인 과정이라 할 수 있는 상하좌우 4방향 탐색을 실시해주고

            if not visited[nx][ny]:
                if field[nx][ny] == '#':
                    visited[nx][ny] = 1
                    continue 

울타리가 나온다면 방문 여부만 표기해주고 continue로 스킵 (공간만 나눌 뿐이지 딱히 할게 없음)

                if field[nx][ny] == '.':
                    visited[nx][ny] = 1
                    que.append([nx,ny])

빈 공간이 나온다면 방문 여부 표기해주고 다음 탐색지점에 추가

                if field[nx][ny] == 'v':
                    visited[nx][ny] = 1
                    field[nx][ny] = 'chk'
                    wolf += 1
                    que.append([nx,ny])

만약 늑대가 나온다면 방문 여부 표기해주고 해당 인덱스 재탐색을 하지 않도록 다른 변수로 치환, 그리고 해당 구역 내에 늑대가 있다는 뜻이니까 늑대의 지역변수 + 1 하고 다음 탐색지점에 추가

                if field[nx][ny] == 'o':
                    visited[nx][ny] = 1
                    field[nx][ny] = 'chk'
                    sheep += 1
                    que.append([nx,ny])

만약 양이 나온다면 방문 여부 표기해주고 해당 인덱스 재탐색을 하지 않도록 다른 변수로 치환, 그리고 해당 구역 내에 양이 있다는 뜻이니까 양의 지역변수 + 1 하고 다음 탐색지점에 추가

하면 됩니다.

마지막으로 저희가 작성한건 지역변수, 그러니까 해당 구역 '내'의 양과 늑대의 마릿수이므로

    if sheep > wolf:
        sheep_ans += sheep 
    else:
        wolf_ans += wolf 

양의 마릿수가 늑대보다 많다면 늑대를 쫓아내므로 양의 최종값에 현 구역 내 양의 마릿수,
아니라면 늑대가 양을 다 잡아먹으므로 늑대의 최종값에 현 구역 내 늑대의 마릿수를 추가해주면 됩니다.

print(sheep_ans,wolf_ans)

마지막으로 출력하면 답이 정상적으로 나오는 걸 확인 할 수 있습니다.