[백준] 2667. 단지번호붙이기

 

📌문제

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

 

🎖️난이도

 

✔️풀이

from collections import deque

n = int(input())
graph = [list(map(int, list(input()))) for _ in range(n)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

danji_num = 0
house_num_list = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            # bfs
            queue = deque()
            queue.append([i, j])

            # 첫 시작점의 nx, ny부터 cnt += 1 해주므로, cnt = 1부터 시작
            cnt = 1 
            graph[i][j] = 0
            while queue:
                x, y = queue.popleft() # 현재는 0이지만 1이었던 곳의 사방면 탐색

                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    if nx in range(n) and ny in range(n):
                        if graph[nx][ny] == 1:
                            queue.append([nx, ny])
                            # x,y가 아니라 현재 nx,ny를 0으로 & cnt++
                            # 1 발견한 곳 다시는 방문하지 않도록!
                            graph[nx][ny] = 0 
                            cnt += 1

            house_num_list.append(cnt)
            
house_num_list.sort()
print(len(house_num_list))
for num in house_num_list:
    print(num)

 

🧠노트

BFS!

 

0으로 graph의 값을 바꿔주고, cnt++를 해주는 부분에서 좀 헤맸당.

(초기값과 if문 내부의 주석 처리된 부분)

 

그리고 결정적으로

queue에 nx, ny 좌표를 넣어준 후 0으로 visited 처리해줄 때

nx, ny 위치가 아닌 x, y 위치에 해줘서 처음에 틀렸었다ㅠ

(popleft한 애의 4방면 이웃들을 탐색하며 1인 곳을 0으로 바꿔주고 cnt++ 해줘야 함!)

 

그래프 탐색 시,

어떤 방식으로 방문 처리를 할 것인지 등등을

정신 똑바로 차리고 구현하자!

 

🔍참고

-