[백준 2667, Silver I] 단지번호붙이기

📒문제

🎈풀이

import sys
from collections import deque

def bfs(row, col):
  q = deque()

  cnt = 0
  drow = [1, -1, 0, 0]
  dcol = [0, 0, 1, -1]

  q.append((row, col))
  arr[row][col] = 2

  while q:
    crow, ccol = q.popleft()
    cnt += 1

    for i in range(4):
      nrow = crow + drow[i]
      ncol = ccol + dcol[i]

      if 0 <= nrow < N and 0 <= ncol < N and arr[nrow][ncol] == 1: 
        q.append((nrow, ncol))
        arr[nrow][ncol] = 2 #방문표시는 이때 해주어야 함
  
  return cnt


N = int(sys.stdin.readline())
arr = []
result = []

for _ in range(N):
  arr.append(list(map(int, sys.stdin.readline().rstrip())))


for i in range(N):
  for j in range(N):
    if arr[i][j] == 1:
      result.append(bfs(i, j))

result.sort()

print(len(result))
for i in range(len(result)):
  print(result[i])

늘상 풀었던 BFS/DFS 문제였지만 워낙 오랜만에 풀다 보니 조금 버벅이는 점이 있었다. 지금 이 코드에선 visit배열을 사용하는 대신에 arr를 2로 표현하는 것으로 방문 지점을 표시했다.

주석에 표기한 방문표시 시점을 헷갈리지 말자.

• 이 코드에서 arr[nrow][ncol] = 2 하는 대신에 arr[crow][ccol] = 2를 해야 된다고 생각할 수 있는데,
  <그림 2>의 예를 들어 q에서 pop처리 됐을때 visit 처리를 해버리면
  (2, 1) 지점과, (1, 2) 지점 에서는 모두 (2, 2)지점이 방문이 되어 있지 않은 상태이기 때문에, 이중으로 q에 (2, 2) 지점을 넣어 cnt가 제대로 세어지지 않는 문제가 있다.

그러니까 잘 기억해두자. ㅎㅎ 이제야 정확한 이유를 알게 되었다.