[백준/Python] 3184번 - 양

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
yard = [list(input().rstrip()) for _ in range(r)]
visited = [[False for _ in range(c)] for _ in range(r)]

# . 빈필드 / # 울타리 / o 양 / v 늑대
def bfs(a, b):
  stack = [(a,b)]
  sheep, wolf = 0, 0
  
  while stack:
    x, y = stack.pop()
    visited[x][y] = True
    # 양, 늑대 개수 세기
    if yard[x][y] == 'o':
      sheep += 1
    elif yard[x][y] == 'v':
      wolf += 1
    
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
      nx, ny = x + dx, y + dy
      if 0<=nx<r and 0<=ny<c and not visited[nx][ny] and yard[x][y] != '#':
        stack.append((nx, ny))
        visited[nx][ny] = True # 와 이거의 유무를 느낌...
  return sheep, wolf

survive_sheep, survive_wolf = 0, 0
for i in range(r):
  for j in range(c):
    if not visited[i][j] and yard[i][j] != '#':
      s, w = bfs(i, j)
      if s > w:
        survive_sheep += s
      else:
        survive_wolf += w

print(survive_sheep,survive_wolf)

와.. 처음 로직은 맞았는데 인접 노드 넣을 때 visited=True 이거 안넣어줘서 계속 틀렸었다.

(근데 예제 코드들은 어떻게 맞았는지 신기하다)

 

저 줄이 중요한 이유는 다음과 같다.

인접 노드들을 stack에 넣어줬는데 True를 해주지 않았다. 그럼 또 같은 노드가 인접 노드로 들어서 양, 늑대 개수가 달라질 수 있게 된다.

bfs에서는 visited 체크를 인접 노드 넣을 때 필요하다!!! 그러므로 인접 노드가 stack에 들어가면 true로 해줘야 한다!

 

고로 아래와 같이 코드를 짜도 무방하다

...
def bfs(a, b):
  stack = [(a,b)]
  visited[a][b] = True
  sheep, wolf = 0, 0
  
  while stack:
    x, y = stack.pop()
    # 양, 늑대 개수 세기
    if yard[x][y] == 'o':
      sheep += 1
    elif yard[x][y] == 'v':
      wolf += 1
...

 

다른 사람 풀이

- Queue 를 이용

- DFS를 이용

- visited를 사용하지 않고, 방문한 자리를 #로 바꿈 -> 울타리(#) 유무만 계속 체크 (시간, 메모리 부분에서 이 코드가 근소하게 효율적이라고 함)

- 처음에 양, 늑대를 카운트해주고 bfs를 돌리면서 - 해줌