실전 DFS, BFS (유형 정리)

DFS, BFS 문제를 풀다보니 어려움이 생겨서 유형을 정리하고자 글을 남긴다.

아무래도 머리가 그닥 좋지 않아서 그런지 이해해서 푸는 것은 아직 어렵기에 대표적인 유형 3가지만 정리하려고 한다.

후에 문제를 많이 풀게 될 경우 추가로 정리할 예정이다.

참고로 여기 있는 코드들은 예시의 문제의 정답이 아님을 알린다.

1. 그래프 형태를 직접 쌍으로 받는 문제들

ex)

https://www.acmicpc.net/problem/1260

(실버 2)

1260번: DFS와 BFS

 

입력값을 보면 다음과 같이 받는다.

 

4 5 1
1 2
1 3
1 4
2 4
3 4

 

간선의 관계를 직접적으로 받아서 표현하는 유형이다.

이런 경우에는 다음과 같은 형태로 그래프를 받고 DFS or BFS를 사용한다.

 

from collections import deque # DFS 구현시 사용하는 collections 모듈

n,m,v=map(int,input().split()) # n은 노드의 수, m은 간선의 수, v는 시작 노드 번호
graph=[[] for _ in range(n+1)] # 노드 수+1만큼 반복해서 2차원 배열 생성

for _ in range(m): # 그래프에서 간선 사이의 관계를 입력받는 과정
	a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

def bfs(graph,v,visited):
	visited[v]=True
    print(v,end=' ') # 결과 출력을 위한 부분
    for i in graph[v]:
    	if not visited[i]:
        	bfs(graph,i,visited)

def dfs(graph,v,visited):
	queue=deque([v])
    visited[v]=True
    while queue:
    	v=queue.popleft()
        print(v, end=' ') # 결과 출력을 위한 부분
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i]=True
                
visited=[False]*(n+1)

bfs(graph,v,visited)
dfs(graph,v,visited)

출력 값의 경우 방문하는 순서를 알려준다.

2. 미로 형태의 문제들

ex)

https://www.acmicpc.net/problem/2178

(실버 1)

2178번: 미로 탐색

입력 값을 보면 다음과 같이 받는다.

4 6
101111
101010
101011
111011

 

이런 경우에는 다음과 같은 BFS를 사용해서 해결한다.(DFS 방식의 경우 추후 공부해서 추가할 예정이다.)

 

from collections import deque # BFS 구현시 사용하는 collections 모듈

n,m=map(int,input().split()) # n은 가로, m은 세로
graph=[]

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

for i in range(n): # 가로 횟수만큼 반복
	graph.append(list(map(int,input())))
    
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=y+dy[i]
      			if nx<0 or ny<0 or nx>=n or ny>=m:
        			continue
      			if graph[nx][ny]==0: # 벽이 1이냐 0이냐에 따라 값이 변경
        			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))

 

출력 값의 경우 특정 시작점에서 도착점까지의 최단 거리를 출력한다.

3. 묶음을 구하는 문제들

ex)

https://www.acmicpc.net/problem/2667

(실버 1)

2667번: 단지번호붙이기

 

입력 값의 경우 2번의 유형과 비슷하거나 똑같이 받는다 하지만 출력 값이 다르게 나온다.

이런 경우에는 다음과 같은 재귀 형태의 DFS를 사용한다. (BFS는 추후에 공부해서 추가할 예정이다.)

 

n,m=map(int,input().split()) # n은 가로, m은 세로
graph=[]
result=0
for i in range(n): # 가로 횟수만큼 반복
	graph.append(list(map(int,input())))
    
def dfs(x,y):
  if x<0 or y<0 or x>=n 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

for i in range(n):
  for j in range(m):
    if dfs(i,j)==True:
      result+=1
print(result)

 

출력 값의 경우 묶음의 갯수가 나온다.