DFS, BFS 문제를 풀다보니 어려움이 생겨서 유형을 정리하고자 글을 남긴다.
아무래도 머리가 그닥 좋지 않아서 그런지 이해해서 푸는 것은 아직 어렵기에 대표적인 유형 3가지만 정리하려고 한다.
후에 문제를 많이 풀게 될 경우 추가로 정리할 예정이다.
참고로 여기 있는 코드들은 예시의 문제의 정답이 아님을 알린다.
1. 그래프 형태를 직접 쌍으로 받는 문제들
ex)
https://www.acmicpc.net/problem/1260
(실버 2)
입력값을 보면 다음과 같이 받는다.
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)
입력 값을 보면 다음과 같이 받는다.
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)
입력 값의 경우 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)
출력 값의 경우 묶음의 갯수가 나온다.
'컴퓨터 CS > 자료구조' 카테고리의 다른 글
BFS-Python(파이썬) (0) | 2022.03.27 |
---|---|
DFS-Python(파이썬) (0) | 2022.03.27 |
자료구조-그래프 Python(파이썬) (0) | 2022.03.24 |
자료구조-트리 Python(파이썬) (0) | 2022.03.24 |