3184

날짜 : 2023. 05.10

사용 언어 : python

 

문제

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

 

 

코드

import sys
from collections import deque
r, c = map(int, sys.stdin.readline().split())
graph = list()
for _ in range(r):
    graph.append(' '.join(sys.stdin.readline().rstrip()).split())
"""for i in graph:
    print(i)"""
visited = [[False] * c for _ in range(r)]
res_s, res_w = 0, 0


def bfs(a, b):
    s, w = 0, 0
    if graph[a][b] == "o": s += 1
    elif graph[a][b] == "v": w += 1
    visited[a][b] = True
    q = deque()
    q.append([a, b])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(r) and ny in range(c):
                if not visited[nx][ny] and graph[nx][ny] != "#":  # 방문 x
                    visited[nx][ny] = True  # 방문처리
                    if graph[nx][ny] == "o": s += 1
                    elif graph[nx][ny] == "v": w += 1
                    else: pass
                    q.append([nx, ny])
    return s, w

for i in range(r):
    for j in range(c):
        if not visited[i][j] and graph[i][j] != "#":  # 방문 x, 울타리 아닌경우
            s, w = bfs(i, j)
            #print(i, j, s, w)
            if s > w:  # 양이 더 많은 경우
                res_s += s
            else:
                res_w += w
print(res_s, res_w)

 

 

풀이

- 이중for 문을 사용해 그래프를 탐색하면서 방문하지 않은 스팟이 울타리(#)가 아닌 경우 해당 구역을 BFS로 탐색한다.

- 탐색하면서 양(o)과 늑대(v)의 개수를 카운트 후 리턴하고, 양의 마리수 > 늑대의 마리수 일 때에는 양이 생존했기 때문에 양의 수를 카운트하고 반대의 경우에는 늑대의 수를 카운트한다.

 

 

알게된 점

- BFS에서 아무것도 없는 케이스('.')를 고려 못해서 애먹었다.

- 조건을 설정하는 데 있어서 조금 디테일하게 잡을 필요가 있는 것 같다.

 

 

참고 사이트

-