코딩테스트 준비하는 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)
'PPS(Algorithm) > DFS BFS' 카테고리의 다른 글
[프로그래머스] Lv2. 숫자 변환하기 python (1) | 2024.01.08 |
---|---|
[백준] 1759. 암호 만들기 - python (0) | 2023.09.11 |
[Baekjoon] 10026. 적록색약(python) (0) | 2022.12.29 |