[Python] DFS/BFS 문제풀이

DFS 풀이법

음료수 얼려 먹기

n, m = map(int, input().split())

graph = []
for i in range(n):
	graph.append(list(map(int, input())))
    
def dfs(x, y):
	if x <= -1 or x >= n or y <= -1 or y >= m:
    	return False
    if graph[x][y] == 0:
    	graph[x][y] = 1
        # 상, 하, 좌, 우의 위치도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False
    
result = 0
for i in range(n):
	for j in range(m):
    	if dfs(i, j) == True:
        	result += 1
print(result)

타겟넘버

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0,0)
    return answer

네트워크

간선 하나로 갈 때의 경우만 보였으므로, DFS 사용

def solution(n, computers):            
    
    def DFS(i):
        visited[i] = 1
        for a in range(n):
            if computers[i][a] and not visited[a]:
                DFS(a)      
                
    answer = 0
    visited = [0 for i in range(len(computers))]
    for i in range(n):
        if not visited[i]:
            DFS(i)
            answer += 1
        
    return answer

BFS 풀이법

미로 탈출

from collections import deque

n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(map(int, input())))
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
	queue = deque()
    queue.append((x, y)
    while queue:
    	x, y = queue.popleft()
    # 현재 위치에서 네 방향으로의 위치 확인
    for i in range(4):
    	nx = x + dx[i]
        ny = x + dy[i]
        # 미로 찾기 공간을 벗어난 경우 무시
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
        	continue
        # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
        if graph[nx][ny] == 1:
        	graph[nx][ny] = graph[x][y] + 1
            queue.append((nx, ny))
     # 가장 오른쪽 아래까지의 최단 거리 반환
     return graph[n - 1][m - 1]
     
print(bfs(0, 0))

타겟넘버

#BFS 풀이
def solution(numbers, target):
    answer = 0
    leaves = [0]
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)
            tmp.append(parent - num)
        leaves = tmp
    for leaf in leaves:
        if leaf == target:
            answer += 1
    return answer

네트워크

from collections import deque

def solution(n, computers):            
    
    def BFS(i):
        q = deque()
        q.append(i)
        while q:
            i = q.popleft()
            visited[i] = 1
            for a in range(n):
                if computers[i][a] and not visited[a]:
                     q.append(a)
                
    answer = 0
    visited = [0 for i in range(len(computers))]
    for i in range(n):
        if not visited[i]:
            BFS(i)
            answer += 1
        
    return answer