dfs,bfs 풀이 방법

DFS : 깊이 우선 탐색 -> 1번 노드를 확인하면 바로 2번노드, 3번노드 ...순으로 확인

BFS : 너비 우선 탐색 -> 1번 노드의 모든 경우 확인 후, 2번 노드의 모든 경우 확인 후 ...

 

문제에서 N(노드), M(간선), V(출발점)과 간선정보가 주어질경우 해당 정보를 가공하는 방법은

graph, visited 리스트처럼 만들어서 가공 후 활용

N,M,V랑 간선정보를 graph랑 visited 리스트로 바꾸기

https://www.youtube.com/watch?v=d3R1s_OmwAk

import sys

def dfs(idx):
	global visited
    visited[idx] = True
    print(idx, end=' ')
    for next in range(1, N+1):
    	if not visited[next] and graph[idx][next]:
        	dfs(next)

def bfs():
	global q, visited
    while q: 						#queue의 요소가 남아있을 때까지 반복
    	cur = q.pop(0) 
        print(cur, end=' ')
        for next in range(1, N+1):
        	if not visited[next] and graph[cur][next]:
            	visited[next] = True
                q.append(next)

input = sys.stdin.readline
N,M,V = map(int, input().split())

# 1. graph 정보 입력
graph = [[False] * (N+1) for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(M):
	a,b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True
    
# 2. dfs
dfs(V)
print()


# 3. bfs
visited = [False] * (N+1)  #dfs로 바뀐 값 초기화
q = [V]
visited[V] = True

 

 

 

프로그래머스 문제 - DFS에서 depth 형식으로 내려가는 것을 구현하는 방법

def solution(numbers, target):
    answer = 0
    
    def dfs(depth, total):
        nonlocal answer
        if depth == len(numbers):
            if total == target:
                answer += 1
            return
        
        dfs(depth+1, total+numbers[depth])
        dfs(depth+1, total-numbers[depth])
    
    dfs(0,0)

    return answer

 

 

프로그래머스 문제 - BFS로 최단경로 구하기

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    visited = [[0] * m for _ in range(n)]
    directions = [(0,1), (1,0), (0,-1), (-1,0)] #(행, 열) -> 동, 남, 서, 북
    
    # BFS를 위한 큐 초기화
    queue = deque( [(0,0,1)] ) #(x,y,distance)
    visited[0][0] = 1
    
    while queue: # 큐가 비어있지 않는 동안 반복
        x,y,dist = queue.popleft()
        
        # 상대 팀 진영에 도착한 경우
        if x==n-1 and y==m-1:
            return dist
        
        # 현재 위치에서 갈 수 있는 모든 방향 탐색
        for dx, dy in directions:
            print(f"dx {dx}, dy {dy}")
            nx, ny = x+dx, y+dy
            
            # 맵 내에 있고, 벽이 아니며, 아직 방문하지 않은 칸인 경우
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 0 and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                queue.append((nx,ny,dist+1))
    
    # 상대 팀 진영에 도달할 수 없는 경우
    return -1

 

프로그래머스 - 노드, 간선으로 그래프 그리기 -> BFS로 최단 경로 중 가장 먼 노드 탐색

from queue import deque
import heapq

def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    
    for n1, n2 in edge:
        graph[n2].append(n1)
        graph[n1].append(n2)
    
    answer_candidate = []
    # 1번 노드부터 나머지 각각의 노드까지 bfs로 최단거리로 가는 dist 구해서 그중 최대인 노드들만 필터링
    visited = [False for _ in range(n+1)]
    visited[0] = True
    visited[1] = True
    queue = deque([(1, 0)]) # [시작 노드, 이동 거리]

    while queue:
        start, dist = queue.popleft()

        for ele in graph[start]:
            if visited[ele] != True:
                visited[ele] = True
                answer_candidate.append(dist+1)
                queue.append((ele, dist+1))
    
    return answer_candidate.count(max(answer_candidate))