BFS / DFS 문제 모음 & 문제 유형 정리

BFS / DFS 의 개념 자체를 모르는 사람은 좋은 블로그 정리글이나 유튜브 영상에서 꼭 배워오세요!!!
해당 글은 BFS / DFS의 문제 유형과 문제 접근법들을 정리한 글 입니다!!

문제 모음

[기초 문제]
1. DFS 와 BFS (백준) : https://www.acmicpc.net/problem/1260

2. Number of islands ( leetcode ) : https://leetcode.com/problems/number-of-islands/

3. keys and rooms ( leetcode ) : https://leetcode.com/problems/keys-and-rooms/description/

4. shortest path in binary matrix ( leetcode )  : https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

5. word search ( leetcode )  : https://leetcode.com/problems/word-search/description/

6. 네트 워크 (프로그래머스) : https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3

7. 단지 번호 붙이기 (백준) : https://www.acmicpc.net/problem/2667

8. 미로 탈출 (백준) : https://www.acmicpc.net/problem/2178

9. 바이러스 (백준) : https://www.acmicpc.net/problem/2606

10. 유기농 배추 (백준) : https://www.acmicpc.net/problem/1012

[응용 문제]
1. 거리두기 확인하기 (프로그래머스) : https://school.programmers.co.kr/learn/courses/30/lessons/81302

2. 스타트 택시  (백준) : https://www.acmicpc.net/problem/19238

문제 유형

문제 유형은 그래프 순회 와 길찾기로 크게 두가지로 나누어진다.

그래프 순회 유형은
1번 노드가 n번 노드로 갈 수 있는지 없는지를 묻는 문제(연결 여부),
BFS 또는 DFS를 사용했을 때 노드의 방문 순서를 묻는 문제(노드 방문 순서) 등이 있다.

길찾기 문제는 1과 0으로 표신된 길과 벽을 주는 것이 국룰 문제이다.
특정 position에서 다른 position으로 이동 가능한지 불가능 한지를 판단하는 문제(도달여부),
1로 모여있는 집단들이 몇개 있는지 파악하는 문제(군집개수),
특정 position에서 다른 position까지 최단거리(BFS 이용한 최단거리 문제) 등이 문제 유형이 있다.

각 유형의 대표 기초 문제들을 보면 다음과 같다.

그래프 순회(연결 여부) : 프로그래머스 네트워크 문제 / 길찾기(군집 개수) : 백준 유기농 배추 문제

 

입력 데이터 부터 크게 차이나서 헷갈릴 일은 없다.

template 코드 

template코드란 가장 기본적인 코드를 의미한다.
코드의 공식 같은 존재이다. 따라서 해당 template코드는 외워야 하며 문제를 읽고 문제유형이 파악되어서 BFS/DFS 문제일 경우 해당 코드를 5분내에 적어야한다.

모든 BFS/DFS 문제는 template코드에서 시작되며 template코드를 활용하고 변형해서 푸는 것들이다.
제발 외우고 시간 측정도 꼭하자. 머리 굴려가면서 template 코드 치면 코딩테스트 이미 지고 시작하는 것이다.

1. 그래프 순회 template 코드

1-1 graph 저장 template코드

n, v  = map(int, input().split()) # 노드 개수, 간선 개수 입력받기

graph = [[] for _ in range(n+1)]

for _ in range(v):
	n1, n2 = map(int, input().split())
	graph[n1].append(n2)
	graph[n2].append(n1) # 양방향 그래프인 경우

 

위와 같은 그래프를 template 코드를 저장하면 다음과 같이 표현된다.

# 단방향 그래프
graph = [
	[],
    [2, 3],
    [3],
    [],
    [3]
]

# 양방향 그래프
graph = [
	[], 
    [2], 
    [1, 3, 4],
    [2, 4],
    [2, 3]
]

1-2 BFS 그래프 순회 template 코드

from collections import deque

# 방문 순서 반환 bfs
def bfs(start):
	q = deque([start])
    
    visited = [False] * (n+1)
    
    result = []
    
    while q:
    	cur_node = q.popleft()
    	
        if visited[cur_node]:
        	continue
            
        visited[cur_node] = True
    	result.append(cur_node)
        
        for nxt_node in sorted(graph[cur_node]):
        	if not visited[nxt_node]:
            	q.append(nxt_node)
    
    return result

1-3 dfs template 코드(stack)

def dfs(start):
	stack = [start]
    
    visited = [False] * (n+1)
    
    result = []
    
    while stack:
    	cur_node = stack.pop()
    	
        if visited[cur_node]:
        	continue
        
        visited[cur_node] = True
        result.append(cur_node)
        
        for nxt_node in sorted(graph[cur_node], reverse=True):
        	if not visited[nxt_node]:
            	stack.append(nxt_node)
    
    return result

 

2. 길찾기 template 코드

2-1 graph 저장 template 코드

row_num, col_num = map(int, input().split())

graph = [[1, 0, 0, 1, 0],
		[1, 1, 0, 1, 0],
        [1, 0, 1, 1, 1],
        [1, 0, 1, 0, 1],
        [1, 1, 1, 0, 1]]

2-2 bfs template 코드

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(start, end):
	q = deque([start])
    visited = [[False] * col_num for _ in range(row_num)]
    
    while q:
    	 cur_y, cur_x = q.popleft()
         
         if visited[cur_y][cur_x] :
         	continue
            
         visited[cur_y][cur_x] = True
            
         for i in range(4):
         	nx = dx[i] + cur_x
            ny = dy[i] + cur_y
            
            if nx < 0 or nx >= col_num or ny < 0 or ny >= row_num:
            	continue
                
            if graph[ny][nx] == 0 or visited[ny][nx]:
            	continue
                
            q.append((ny, nx))

2-3 dfs template 코드

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def dfs(start):
	stack = [start]
    visited = [[False] * col_num for _ in range(row_num)]
    
    while stack:
    	cur_y, cur_x = stack.pop()
        
        if visited[cur_y][cur_x]:
        	continue
        
        visited[cur_y][cur_x] = True
        
        for i in range(4):
        	nx = dx[i] + cur_x
            ny = dy[i] + cur_y
            
            if nx < 0 or nx >= col_num or ny < 0 or ny >= row_num:
            	continue
                
            if visited[ny][nx] or graph[ny][nx] == 0:
            	continue
                
            stack.append((ny, nx))