[python] BOJ 2667 단지번호붙이기

BOJ 2667 단지번호붙이기

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

2667번: 단지번호붙이기

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

접근

문제에서 요구하는 사항은 두가지이다.

1. 단지 수 출력

2. 각 단지 별 집의 수를 오름차순으로 출력

 

먼저 단지 수 출력은 dfs 또는 bfs의 호출횟수를 카운트하면 된다. 한번의 탐색을 통해서 연결된 모든 집을 탐색하게 되므로 호출을 한 횟수가 단지의 수가 된다.

 

각 단지 별 집의 수는 dfs 또는 bfs 수행 과정에서 스택이나 큐에 삽입한 횟수를 세아리면 된다.

이 문제의 경우에는 2차원 배열로 정사각형 모양의 지도를 표현했을때 값이 1인 경우가 이에 해당한다.

 

DFS를 활용한 풀이 코드

먼저 DFS를 통해 문제를 해결해보자.

def dfs(x,y):     global cnt     if x<=-1 or x>=N or y<=-1 or y>=N:         return False     #방문하지않은 노드 방문처리하고 인접노드에 대해서 방문     if graph[x][y] == 1:         graph[x][y] = 0         cnt += 1         #인접노드 방문         dfs(x-1,y)         dfs(x+1,y)         dfs(x,y-1)         dfs(x,y+1)         return True     return False     N = int(input()) graph = [] global cnt cnt = 0 danzi_n = 0 danzi_cnt = [] for i in range(N):     graph.append(list(map(int,input()))) for i in range(N):     for j in range(N):         # 정사각형 각 정점에 대해서         flag = dfs(i,j)         if flag == True:             danzi_n += 1             danzi_cnt.append(cnt)             cnt = 0 danzi_cnt.sort() print(danzi_n) for i in danzi_cnt:     print(i)

각 정점에서 dfs를 호출한 뒤에 dfs 호출 결과가 True 일때 단지 수를 1 증가한다. 

dfs 함수를 살펴보면, 현재 단지가 방문하지않은 상태 즉 값이 1일때 True를 반환한다.

 

다시 말하면, 방문하지않은 정점에서의 dfs 호출일 경우 True를 반환한다.

위에 표시된 3개의 정점에서의 dfs 호출만 True를 반환한다. 왜냐하면 한번의 호출에서 연결된 단지를 모두 탐색하기때문이다. 따라서 단지 수는 3이 된다.

 

다음으로 각 단지 별 집의 수는 아까 밀했듯이 스택에 삽입되는 집의 수를 세아리는 것인데, 위의 코드에서는 재귀함수가 호출되면서 스택에 쌓이는 수를 세아려야한다.

전역변수 cnt를 사용해서 각 dfs 호출에서 인접노드가 몇개있는지 세아려주면 된다.

 

 

BFS를 활용한 풀이코드

from collections import deque def bfs(graph,x,y,index):     queue = deque()     queue.append((x,y))     cnt = 0     flag = False     while queue:         x, y = queue.popleft()         for i in range(4):             nx = x + dx[i]             ny = y + dy[i]             if nx < 0 or nx >= N or ny <0 or ny >=N:                 continue             if graph[nx][ny] == 0:                 continue             if graph[nx][ny] == 1:                 # print("@nx,ny",nx,ny)                 flag = True                 cnt+=1                 graph[nx][ny] = index                 queue.append((nx,ny))           if flag:         return cnt     else:         return 1                                N = int(input()) graph = [] for i in range(N):     graph.append(list(map(int,input()))) #상,하,좌,우 방향 벡터 설정 dx = [-1,1,0,0] dy = [0, 0, -1,1] index=2 cnt =[] res = 0 for i in range(N):     for j in range(N):        if graph[i][j] == 1:            cnt.append(bfs(graph,i,j,index))            index += 1            res += 1 #print cnt.sort() print(res) for c in cnt:     print(c) # for gra in graph: #     print(gra)

 

 

 

 

 

단지별로 붙이는 번호는 첫번째 집부터 1,2,3 , .... 이 아닌 2,3,4부터 시작했다.

그림과 다르게 첫번째 집을 1번으로 설정하지않은 이유는, 집이 있는지 판단할 때의 조건과 겹치기때문에

첫번째 단지 번호를 2번부터 설정해서 풀었다.

 

따라서 1번 입력에 대한 결과 그래프를 다음과 같이 표현해서 해결했다.

그리고 조금 헤맸던 부분을 얘기하면,  다음과 같은 예시에서다.

 

5
10101
01111
11111
01011

10111

 

bfs 수행과정에서 단지 내 1의 개수를 세아리는 방식으로 집의 개수를 구하려고 했는데

위의 예시처럼 단지 내 집의 개수가 1개인 경우, 큐가 바로 비어버려서 bfs가 수행이 되지않고 끝나버리기때문에

집의 개수가 0으로 반환된다. 이 경우는 따로 예외처리를 해서 작성했다.