백준 (#2667) 단지 번호 붙이기 (Python)

문제 링크

링크

 

풀이

이제 어느 정도 bfs를 풀다보니 이런 구현 기반 bfs 문제에 대한 감이 잡힌다. 지도 위에서 인접한 곳에 뭔가를 찾는다거나 바꾼다거나 할 때 흐름을 보면

 

1. dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]과 같이 x, y를 기준으로 위/아래/양옆으로 갈 수 있는 방향을 설정한다.

 

2. 문제에서 주어지는 지도를 MAP이라 하고 해당 위치를 방문했는지 체크하는 지도를 visited로 새로 생성한다. (아직 어디도 방문하지 않았으니 전부 방문 X로 체크. False로 만들어도 되고 0으로 만들어도 되는데 지금 문제와 같이 각 구역마다 새로운 번호를 매길 때는 0으로 만들어놓고 서로 다른 구역에 대해 다른 번호를 매기는 식으로 해도 괜찮을듯.)

 

3. 이중 for문을 돌면서 해당 지도에서 값이 들어있고 방문하지 않은 곳을 찾는다.

4. 한 지점을 찾으면 그걸 queue에 append.

5. while문을 돌면서 q에 값이 없을 때까지 while문을 돌린다.

6. 위에서 q에 삽입한 가장 첫번째 값을 popleft로 빼낸다.

7. 해당 지점을 기준으로 위/아래/양옆을 for문으로 돌면서 (nx, ny = x+ dx, y + dy)

• nx, ny가 지도 범위 안에 있는지
• MAP[nx][ny]에 값이 들어있는지
• visited[nx][ny]에 아직 방문하지 않았는지

이 세 가지를 체크한다. 여기서 주의해야 할 점은 3번, 7번에서 모두 MAP에 값이 있고 visited에 방문하지 않았는지 체크해줘야 한다는 점. 위에서 했다고 아래서 안하면 방문한 애들을 중복해서 체크하거나 하는 문제가 일어난다.

8. 7에서 셋을 모두 만족하면 [nx, ny]를 queue에 appned.

이를 계속 반복해 이중 for문이 끝날 때까지 돌리면 끝!

 

여기서 문제마다 구획이 몇 개인지를 센다거나 하는 배리에이션이 나타나는데, 적절한 위치에 count를 추가해주면 된다. 해당 구역을 셀 때는 동일한 구역을 다 방문하고 더이상 방문할 곳이 없을 때 count+=1을 해줘야 해당 구역마다 하나씩 셀 수 있다는 점.

 

단지 번호 문제도 위의 개략적인 흐름을 따라서 풀면 된다. 정답 코드는 아래.

 

 

코드

from sys import stdin
from collections import deque

n = int(stdin.readline())

homes = [list(map(int, list(stdin.readline().strip()))) for _ in range(n)]
ans = [0]
visited = [[0] * n for _ in range(n)]

def bfs():
    vil_num = 1
    q = deque()
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    for i in range(n):
        for j in range(n):
            if homes[i][j] != 0 and visited[i][j] == 0:
                cnt = 0
                q.append([i, j])
                visited[i][j] = vil_num
                while q:
                    x, y = q.popleft() 
                    
                    for m in range(4):
                        nx = x + dx[m] # 변수 조심! for 문 안에 for 문 돌릴 때 변수 다른 거 쓰기
                        ny = y + dy[m]
                        
                        if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0 and homes[nx][ny] != 0:
                            visited[nx][ny] = vil_num
                            q.append([nx, ny])
                            cnt += 1
                            
                ans.extend([cnt])
                vil_num += 1
    return vil_num-1


vil_num = bfs()
ans.sort()
print(vil_num)
for i in ans[1:]:
    print(i)