백준 2667 : 단지번호붙이기

기초적인 탐색 문제이다.

 

이 문제는 BFS와 DFS 모든 방법으로 풀 수 있는 문제인데, 나는 어제 BFS를 활용한 탐색 문제를 풀었으니 오늘 이 문제는 DFS로 풀기로 했다.

 

import sys
apart = []
N = int(sys.stdin.readline())
for _ in range(N):
    apart.append([*map(int, sys.stdin.readline().strip())])
total = 0
cnt = 0
res = []
def dfs(x, y):
    global cnt
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
    if apart[x][y] == 0:
        return False
    if apart[x][y] == 1:
        cnt += 1
        apart[x][y] = 0
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x + 1, y)
        dfs(x, y - 1)
        return True
for i in range(N):
    for j in range(N):
        if dfs(i, j):
            total += 1
            res.append(cnt)
            cnt = 0
res.sort()
print(total)
for _ in res:
    print(_)

 

개인적으로 global을 사용하는 것이 영 마음에 걸려서,

global을 사용하지 않고 푼 버전도 함께 제출해서 맞았다.

 

import sys
apart = []
N = int(sys.stdin.readline())
for _ in range(N):
    apart.append([*map(int, sys.stdin.readline().strip())])
total = 0
res = []
def dfs(x, y, cnt):
    if x < 0 or x >= N or y < 0 or y >= N:
        return False, cnt
    if apart[x][y] == 0:
        return False, cnt
    if apart[x][y] == 1:
        cnt += 1
        apart[x][y] = 0
        cnt = dfs(x - 1, y, cnt)[1]
        cnt = dfs(x, y + 1, cnt)[1]
        cnt = dfs(x + 1, y, cnt)[1]
        cnt = dfs(x, y - 1, cnt)[1]
        return True, cnt
for i in range(N):
    for j in range(N):
        a, b = dfs(i, j, 0)
        if a:
            total += 1
            res.append(b)
            cnt = 0
res.sort()
print(total)
for _ in res:
    print(_)

 

근데 이렇게 풀어놓고 보니까 그냥 차라리 BFS를 쓰거나, DFS 함수 선언을 안하고 스택과 반복문으로 푸는게 더 깔끔했을 것 같다...

---

문제의 출력 조건에서 집의 개수를 오름차순으로 출력하라는 것을 못 읽고 두번이나 틀렸다.

코딩 테스트에서 낭패를 보지 않으려면 역시 문제를 빠짐없이 잘 읽어야 한다.