[Python] BOJ 2667 - 단지번호붙이기(DFS)

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

이번엔 DFS로 푼 문제이다.

dfs함수:

  m[x][y] = 0을 해줌으로써 방문했다는 표시를 해준다.

  전에 올린 문제와 비슷하게 nx, ny에 x + dx[i], y + dy[i]를 넣고 탐색한다.

  BFS는 nx, ny를 방문하지 않았을 경우, (nx,ny)를 deque에 넣고 방문처리를 해줬는데

  DFS는 재귀방식으로 dfs함수를 또 호출한다. 매개변수로 cnt+1을 넘겨줌으로써 현재 단지에 속하는

  집의 수를 증가시키고 다음 탐색할 nx,ny도 넘겨준다.

  return cnt로 탐색이 끝나면 집의 수를 return 해준다.

 

1. N * N의 지도를 입력받고 단지를 넣을 dab배열 생성

2. (0,0)부터 (N,N)까지 돌면서 m[i][j]가 1이라면 dfs(1, i, j)실행 -> 이어져 있는 집들을 다 count해주면서 0으로 만듬

   dab배열에 각 단지별로 집의 수(cnt)가 append됨.

3. len(dab)으로 단지 수를 출력하고 집의 수를 오름차순으로 정렬해서 출력해야 하므로 sorted(dab)을 한 다음

   차례대로 한 줄씩 출력한다.

import sys
input = sys.stdin.readline
N = int(input())
def dfs(cnt, x,y):
	m[x][y] = 0
	dx = [1,-1,0,0]
	dy = [0,0,1,-1]
	for i in range(4):
		nx, ny = x + dx[i], y + dy[i]
		if 0 <= nx < N and 0 <= ny < N and m[nx][ny] == '1':
			cnt = dfs(cnt+1, nx, ny)
	return cnt
m = [list(input()) for _ in range(N)]
dab = []
for i in range(N):
	for j in range(N):
		if m[i][j] == '1':
			dab.append(dfs(1, i, j))
print(len(dab))
for i in sorted(dab):
	print(i)