[코테]99클럽 코테스터디 8일차 TIL 백준 2667 단지번호붙이기

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

이 문제는 DFS와 BFS모두 풀이가 가능한 문제이다.

나는 BFS로 풀었는데, 사실 BFS는 구현하기가 어렵진 않았지만, 잊어버린 부분이 몇가지 있다. 

방문 리스트를 초기화할때, 

visited = [[False] * N] * N

이런식으로 하게되면, visited 배열의 모든 행이 같은 리스트 객체를 참조하도록 만들기 때문에, 나중에 방문처리를 하게 될때, 한 행의 값을 수정하면, 모든 행의 값이 동시에 변경된다. 

visited = [[False for _ in range(N)] for _ in range(N)]

 

이렇게 초기화 해야한다!

---

또 주의해야할 부분은 bfs(0,0)만 하게 되면 단지 하나만 탐색하고 끝나버리는데, 이를 방지하기 위하여 이중 for문으로 모든 좌표에 대하여 bfs를 수행했었다. 그런데 굳이 다 탐색할 필요는 없고, 방문을 안한 좌표 이면서 그래프 값이 1인 것에 대해서만 탐색하면 됐었는데, 그 포인트를 생각하지 못하는 바람에 틀려버렸다. 

num_danji = 0

results = []

for i in range(N):

    for j in range(N):

        result = bfs(i,j)

        if result != 0:

            num_danji += 1

            results.append(result)

print(num_danji)

이 코드가 아니라, 

num_danji = 0

results = []

for i in range(N):

    for j in range(N):

        # graph[i][j] == 1 이고, 방문하지 않은 곳에서만 BFS 호출

        if graph[i][j] == 1 and not visited[i][j]:

            num_danji += 1

            results.append(bfs(i, j))

print(num_danji)  # 단지 수 출력

for result in sorted(results):  # 각 단지 크기 오름차순 출력

    print(result)

이렇게 해야한다!

전체 코드는 다음과 같다. 

import sys

from collections import deque

read = sys.stdin.readline

N = int(read())

graph = []

for _ in range(N):

    graph.append(list(map(int,list(read().rstrip()))))

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

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

visited = [[False for _ in range(N)] for _ in range(N)]

def bfs(x,y):

    queue = deque([(x,y)])

    visited[x][y] = True

    cnt = 1

    while queue:

        x, y = queue.popleft()  

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1 and not visited[nx][ny]:

                queue.append((nx,ny))

                visited[nx][ny] = True

                cnt += 1

    return cnt

num_danji = 0

results = []

for i in range(N):

    for j in range(N):

        # graph[i][j] == 1 이고, 방문하지 않은 곳에서만 BFS 호출

        if graph[i][j] == 1 and not visited[i][j]:

            num_danji += 1

            results.append(bfs(i, j))

print(num_danji)  # 단지 수 출력

for result in sorted(results):  # 각 단지 크기 오름차순 출력

    print(result)