[python] 백준 3184번: 양(BFS)

# 3184 양

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

3184번: 양

⭐ 코드

import sys
input = sys.stdin.readline

from collections import deque

R, C = map(int, input().split())
graph = [list(map(str, input().strip())) for _ in range(R)]
visited = [[0] * C for _ in range(R)]

dx, dy = [0,0,-1,1], [-1,1,0,0]

def bfs(i,j, sheep, wolf):
    queue = deque()
    queue.append((i,j))
    visited[i][j] = 1 # 방문처리

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 > nx or nx >= R or 0 > ny or ny >= C:
                continue
            
            if graph[nx][ny] == 'v' and visited[nx][ny] == 0: # 늑대일때
                wolf += 1
                visited[nx][ny] = 1
                queue.append((nx,ny))
            
            if graph[nx][ny] == 'o' and visited[nx][ny] == 0: # 양일때
                sheep += 1
                visited[nx][ny] = 1
                queue.append((nx,ny))

            if graph[nx][ny] == '.' and visited[nx][ny] == 0: # 공간일때
                visited[nx][ny] = 1
                queue.append((nx,ny))
    if wolf >= sheep:
        sheep = 0
    elif wolf < sheep:
        wolf = 0
    return [wolf, sheep]

wolf_result = 0
sheep_result = 0
all_result = 0
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'v' and visited[i][j] == 0:
            wolf = 1
            sheep = 0
            all_result = bfs(i,j, sheep, wolf)
            wolf_result += all_result[0]
            sheep_result += all_result[1]
        if graph[i][j] == 'o' and visited[i][j] == 0:
            wolf = 0
            sheep = 1
            all_result = bfs(i,j, sheep, wolf)
            wolf_result += all_result[0]
            sheep_result += all_result[1]
            
print(sheep_result, wolf_result)

📝 풀이

울타리 안에 양과 늑대를 카운트해줘야 하는 문제이다. 문제에서 주어진 조건처럼 울타리 안에 양의 수가 늑대의 수보다 많으면 양이 늑대를 쫓아내고, 양과 늑대의 수가 같거나 늑대의 수가 같으면 양이 다 잡아먹힌다. 

 

내가 짠 코드의 접근 방식은 그래프를 탐색하다가 v(늑대)와 o(양)을 만날때마다 bfs를 실행시켜주는 코드를 작성했다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline

from collections import deque

R, C = map(int, input().split())
graph = [list(map(str, input().strip())) for _ in range(R)]
visited = [[0] * C for _ in range(R)]

dx, dy = [0,0,-1,1], [-1,1,0,0]

일반적인 bfs처럼 graph와 visited를 생성해주고 방향탐색을 위한 dx, dy를 만들어준다.

def bfs(i,j, sheep, wolf):
    queue = deque()
    queue.append((i,j))
    visited[i][j] = 1 # 방문처리

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 > nx or nx >= R or 0 > ny or ny >= C:
                continue
            
            if graph[nx][ny] == 'v' and visited[nx][ny] == 0: # 늑대일때
                wolf += 1
                visited[nx][ny] = 1
                queue.append((nx,ny))
            
            if graph[nx][ny] == 'o' and visited[nx][ny] == 0: # 양일때
                sheep += 1
                visited[nx][ny] = 1
                queue.append((nx,ny))

            if graph[nx][ny] == '.' and visited[nx][ny] == 0: # 공간일때
                visited[nx][ny] = 1
                queue.append((nx,ny))
    if wolf >= sheep:
        sheep = 0
    elif wolf < sheep:
        wolf = 0
    return [wolf, sheep]

그 후에 bfs 함수를 만들어준다. i,j라는 좌표값을 받아주고, sheep인지 wolf인지를 구분하기 위한 인자를 받아준다.

처음의 좌표값을 queue에 삽입해주고 visited[i][j]를 방문처리해준다. queue가 빌때까지 while문을 실행시켜주면서 방향탐색을 해주고, 우리안에 늑대가 있고, 방문한적 없다면 ( graph[nx][ny] == 'v' and visited[nx][ny] == 0 ) wolf에 += 1을 해주고 방문처리를 해주면서 좌표값을 queue에 삽입시켜준다. 동일하게 늑대일때와 빈공간일때의 로직을 실행시켜준다.

 

queue를 다 돌고나서 wolf와 sheep을 비교하면서 wolf 가 크거나 같으면 sheep을 0으로 만들어주고 sheep이 많다면 wolf를 0으로 만든 다음에 리스트에 담아서 return해준다.

wolf_result = 0
sheep_result = 0
all_result = 0
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'v' and visited[i][j] == 0:
            wolf = 1
            sheep = 0
            all_result = bfs(i,j, sheep, wolf)
            wolf_result += all_result[0]
            sheep_result += all_result[1]
        if graph[i][j] == 'o' and visited[i][j] == 0:
            wolf = 0
            sheep = 1
            all_result = bfs(i,j, sheep, wolf)
            wolf_result += all_result[0]
            sheep_result += all_result[1]
            
print(sheep_result, wolf_result)

최종적으로 그래프를 탐색하면서, grpah[i][j]가 'v'이고 방문한적 없는 곳이라면 wolf = 1로 설정해주고 bfs를 실행한 값을 all_result에 담아준다. 리스트에 담긴 값을 wolf_result와 sheep_result에 더해주고, 동일하게 양일 경우일때도 bfs를 실행시켜준다. 그래프를 다 탐색하고 나면 sheep_result와 wolf_result를 출력시켜준다.