[백준 - DFS] 2667 - 단지 번호 붙히기 - 파이썬
by Dojin Kim
2667 - 단지 번호 붙히기 [DFS]
출처 : 백준 2667 단지 번호 붙히기
문제
단지에 대한 정보가 2D 배열의 형태로 주어진다. 1이라는 숫자가 서로 상하좌우로 인접해 있으면 하나의 단지로 간주 된다. 이 때, 총 몇개의 단지가 있고 각 단지별로 몇개의 아파트들이 있는지 센 다음에 오름차순으로 정렬을 하는 것이 문제이다.
이 문제는 기본 DFS로 풀 수 있는 문제이다. 처음에 방문여부에 대한 2D배열을 함께 선언을 해준다. 그 다음에 단지에 대한 2D 배열을 순회하면서 방문하지 않은 칸이고 ‘1’로 시작된다면 DFS를 진행하면 된다. DFS를 진행하면서 1을 마주할 때마다 +1을 해줘서 그 단지내에 아파트가 총 몇개인지 센 다음에 리턴을 한다. 이 정보들을 가지고 있다가 2D 배열 순회가 끝나면, 오름차순으로 정렬을 하고 print를 한다.
주의 sys.setrecursionlimit을 지정해주지 않으면 Python3에서는 문제를 통과할 수 없다. Recursion으로 인해서 스택을 쌓기 때문에 너무 깊게 들어가면 오래걸리기도하고 메모리도 많이 먹어서인 걸로 예상된다. 위 명령어를 작성하면 통과를 할 수 있다.
풀이
# BOJ 2667 - 단지번호붙히기
import sys
sys.setrecursionlimit(100000)
r = sys.stdin.readline
# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def dfs(x, y, cnt):
for m in range(4):
nx = x + dx[m]
ny = y + dy[m]
if (0 <= nx < N) and (0 <= ny < N) and not visited[nx][ny] and zone[nx][ny] == '1':
visited[nx][ny] = True
cnt = dfs(nx, ny, cnt) + 1
return cnt
N = int(r())
zone = [list(map(str, r().strip())) for _ in range(N)]
ans = []
visited = [[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if zone[i][j] == '1' and not visited[i][j]:
visited[i][j] = True
ans.append(dfs(i, j, 1))
print(len(ans))
for i in sorted(ans):
print(i)
Subscribe via RSS
