[Baekjoon] 2667. 단지번호붙이기(python)

코딩테스트 준비하는 Notion Link

https://joowhan.notion.site/PPS-Coding-Test-74f06c5242df4f67807d765869394bb4

 

기억해야 하는 것은,

1. DFS는 깊이 탐색이다.

2. DFS는 Stack을 이용한다. 

그걸 알면서도 막상 문제를 풀려고 하면 잘 모르겠다.

이 문제는 처음에 풀지 못해서 풀이 영상을 보고 다시 풀었다.

DFS에서 중요한 것은 재귀함수를 통해 stack을 사용한다는 것이며 이는 잘 알고 있었지만, 이 문제의 핵심은 DFS했을 때 방문한 node의 수까지 알아야 한다는 것이다. 이 부분을 어떻게 해야 하는지 잘 몰랐는데, 해결책의 간단하다.

return 값을 1로 준 다음 재귀함수에서 나왔을 때에 이 return 값을 더해주면 되는 것이다.

코드로 보면 다음과 같다.

n = int(input())
graph = [[] for _ in range(n)]
for i in range(n):
    graph[i] = list(map(int, input()))

def dfs(x,y):
    result = 1
    if x<0 or y< 0 or x>=n or y >=n or graph[x][y] == 0:
        return 0
    if graph[x][y] == 1:
        graph[x][y] = -1
        result += dfs( x, y-1) #up
        result += dfs( x, y+1) #down
        result += dfs( x-1, y) #left
        result += dfs( x+1, y) #right
    else: return 0
    return result
    
# dfs는 깊이 탐색이다. 현재 graph에서는 어디든 갈 수 있다. 1이면 방문처리하고 count 
count = 0
lis = []
for i in range(n):
    for j in range(n):
        wow = dfs(i,j)
        if wow >0:
            count +=1
            lis.append(wow)
lis.sort()
print(count)
for home in lis:
    print(home)