깊은 부분을 우선적
으로 탐색하는 알고리즘스택
자료구조(혹은 재귀
함수)를 이용하며, 구체적 동작과정은 다음과 같음탐색시작노드
를 스택에 삽입
하고 방문
처리최상단 노드
에 방문하지 않은 인접한 노드
가 하나라도 있으면, 그 노드를 스택에 넣고
방문
처리모두 방문
했으면) 스택에서 최상단 노드를 꺼냄
스택에서 6번 노드를 꺼냄
# 각 노드가 연결된 정보를 표현 (2차원 리스트) graph =[ #0 [], #1 [2,3,8], #2 [1,7], #3 [1,4,5], #4 [3,5], #5 [3,4], #6 [7], #7 [2,6,8], #8 [1,7] ] # 각 노드가 방문된 정보를 표현(1차원 리스트) visited = [False] * 9 # False = 한 번도 인접하지 않는 것으로 초기화 # 정의된 DFS 함수 호출 dfs(graph, 1, visited)
# DFS 메서드 정의 # v = 인덱스로 해석됨 def dfs(graph, v, visited): # 현재 노드 방문처리 visited[v] = True print(v, end=' ') # 현재노드와 연결된 # 다른 노드를 재귀적 방문 for i in graph[v]: if not visited[i]: # visited[v] = True가 아니면 dfs(graph, i, visited) >>> 1 2 7 6 8 3 4 5
N x M 크기의 얼음 틀이 있다.
구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우, 서로 연결 돼 있는 것으로 간주한다.
이 때, 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성해라. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.
💡 DFS를 활용하는 알고리즘은 다음과 같다.
1. 특정지점의 주변 상,하,좌,우를 살펴본 뒤 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있으면 방문
2. 방문한 지점에서 다시 상,하,좌,우를 살펴본 뒤 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문 가능
3. 모든 노드에 대해 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트
💡 Cording
# 그래프 가로 세로 입력 N, M = map(int, input().split()) ------------------------------------------------------------------------------------- # (▼예시) : 그래프 입력 N번의 row 입력 # 2, 3 # 0 1 1 # 0 0 1 graph=[] for i in range(N): graph.append(list(map(int,input().split()))) ------------------------------------------------------------------------------------- def dfs(x, y) : # 그래프 범위를 벗어났으므로 False if x <= -1 or x >= n or y <= -1 or y >=n : return False ------------------------------------------------------------------------------------- # 그래프 x,y좌표가 0이면, 1로 바꿔준다. # 그리고 상, 하, 좌, 우를 살펴보며 1로 바꿔준다. # 어차피 한 덩어리를 cnt +=1 하기 때문에 1개만 0이어도 cnt된다. if graph[x][y] == 0: graph[x][y] = 1 # 상, 하, 좌, 우 좌표를 살펴본다. dfs(x-1, y) #상 dfs(x+1, y) #하 dfs(x, y-1) #좌 dfs(x, y+1) #우 return True ------------------------------------------------------------------------------------- return False # 0이 아니면 False ------------------------------------------------------------------------------------- # 💡Tip: def 함수가 앞에 있어야 호출이 가능함 # 모든 좌표를 살펴보며, dfs가 True이면 cnt+=1 cnt = 0 for i in range(N): for j in range(M): if dfs(i,j) == True: cnt += 1 ------------------------------------------------------------------------------------- print(cnt)
- DFS 문제풀이 연상과정
- 그래프 입력 범위 : n by m
- 그래프 입력 : row 하나씩
- for문으로 순차적인 그래프 좌표이동 구현
- dfs 함수 구현