🟩 [백준] [Python] 3184번_양

문제

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

3184번: 양

풀이

# 백준 3184번 문제 - 양
from collections import deque
r, c = map(int, input().split())
graph = [list(map(str, input())) for _ in range(r)]
dx, dy = [0,0,-1,1], [1,-1,0,0]
def bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    global count_sheep, count_wolf

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= r or ny < 0 or ny >= c: # 범위를 벗어나 탈출을 할 수 있는 경우
                count_wolf = -1
                count_sheep = -1
                break
            elif 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
                if graph[nx][ny] == '#':
                    visited[nx][ny] = 1
                    continue
                elif graph[nx][ny] == '.':
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                elif graph[nx][ny] == 'o':
                    count_sheep += 1
                    visited[nx][ny] = 1
                    q.append((nx, ny))
                else:
                    count_wolf += 1
                    visited[nx][ny] = 1
                    q.append((nx, ny))
    
    return count_sheep, count_wolf

visited = [[0]*c for _ in range(r)]
res = [0,0]
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'v' and not visited[i][j]: # 늑대가 사냥을 시작
            count_sheep = 0
            count_wolf = 1 # 늑대 한마리로 시작
            cnt = bfs(i, j)
            if cnt[1] == -1: # 늑대 혼자 있는 경우 
                continue
            if cnt[0] > cnt[1]: # 양이 늑대보다 많은 경우
                res[0] += cnt[0]
            else: # 늑대가 양보다 많거나 같은 경우
                res[1] += cnt[1]
        elif graph[i][j] == 'o' and not visited[i][j]: # 양이 사냥 시작
            count_sheep = 1 # 양 한마리로 시작
            count_wolf = 0
            cnt = bfs(i, j)
            if cnt[0] == -1: # 양 혼자 있는 경우
                continue
            if cnt[0] > cnt[1]: # 양이 늑대보다 많은 경우
                res[0] += cnt[0]
            else: # 늑대가 양보다 많거나 같은 경우
                res[1] += cnt[1]
for i in res:
    print(i, end=' ')

이번 문제는 BFS를 통해 풀었다. 

처음에 문제를 보고 그렇게 시간이 걸릴거 같지 않았지만 문제를 제대로 읽지 않아서 시간이 오래 걸린 문제였다. 

일단 조건에서 범위를 벗어나게 되면 그것은 어떤 영역에도 속하지 않는다고 하였는데 이 조건을 생각하지 못해서 자꾸 틀렸다고 오류가 났다. (테스트 케이스에서는 이 조건을 만족하는 케이스가 없음)

그래서 늑대가 사냥을 시작할때와 양이 사냥을 시작할때로 나누어 케이스를 구분하였다. 

 

 #(울타리)를 만나면 지나가지 못하므로 continue

.을 만나게 된다면 다음으로 넘어 갈 수 있으므로 q에 삽입해주고 방문처리 후 넘어간다. 

그리고 o는 양을 세주는 변수를 1증가, v는 늑대를 세주는 변수를 1증가 하여 답을 구하였다. 

BFS가 끝나게 되면 양과 늑대의 마리수를 비교 후 더 큰 값을 res에 저장한다.