예제는 다음 그래프를 따름
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]1. DFS
- 깊이 우선 탐색 ⇒ 이론적으로 Stack구조를 사용한다
- 정의
- 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 2-1. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 놓고 방문처리
- 2-2. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
- 2-1, 2-2 과정을 더 이상 수행할 수 없을 때까지 반복
- 구현은 재귀함수를 통해 하면 된다
- 넣고 방문 안했으면 방문처리 & 내 인접 Node들을 재귀적으로 DFS
- 방문 했으면 pass
- 예시로 dfs(1) -> dfs(2),dfs(3),dfs(8) : 이런 식으로 점점 깊어져가면 된다
- 관련 예제 : 얼음의 개수
- 구현
visited = [0] * len(graph)
visited[0] = 1 # index 0는 번호를 위해 추가하였으므로
def DFS(node):
if visited[node] == 0:
visited[node] = 1 #방문처리하고
print(node,end=" ")
for n in graph[node]:
DFS(n) #재귀
DFS(1) ##1 2 7 6 8 3 4 5
2. BFS
- 너비 우선 탐색
- 정의
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다
- 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다
- 구현은 Queue를 이용하면 된다 (내 생각은 굳이 재귀 필요 x)
- 큐를 선언
- 제일 첫 번째 넣고 방문 처리
- 반복 (Queue가 빌 때까지)
- popleft() : 출력
- 뽑은 애의 하위 인자들 중 방문하지 않은 애들 모두 append
구현
def bfs(graph,visited,start):
queue = deque() #큐를 생성
queue.append(start) #queue에 넣기
visited[start] = True #방문처리하고
while (queue): #큐가 빌때 까지
v = queue.popleft() #꺼내면서
print(v , end =" ")
for itm in graph[v]: #꺼낸 녀석의 하위 Node들 추가
if visited[itm] == False: #방문하지 않았으면
queue.append(itm) #넣고
visited[itm] = True #방문처리
else: pass
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False]*9
bfs(graph,visited,1) #1 2 3 8 7 4 5 6
예제
내 풀이
from collections import deque
def bfs(x_start, y_start): #대각선으로만 움직임 우하향으로 이동한다는 점을 이용
global sol, N, M
queue.append((x_start, y_start))
while (queue): #Queue가 빌때까지
sol += 1 #시작점을 포함하므로
v_x, v_y = queue.popleft() #unpacking
if v_x != N-1 :
if graph[v_x+1][v_y] == 1:
queue.append((v_x+1,v_y))
if v_y != M-1:
if graph[v_x][v_y+1] == 1:
queue.append((v_x,v_y+1))
#input 받아오기
graph = []
sol = 0
queue = deque()
N,M = map(int, input().split())
for _ in range (N):
graph.append(list(map(int,list(input()))))
bfs(0,0)
print(sol)
이코테 풀이
from collections import deque
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 소스코드 구현
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복하기
while queue:
x, y = queue.popleft()
# 현재 위치에서 4가지 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 미로 찾기 공간을 벗어난 경우 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n - 1][m - 1]
# BFS를 수행한 결과 출력
print(bfs(0, 0))
구현은 Queue를 이용하면 된다 → 내 생각은 굳이 재귀 필요 x
from collections import deque
큐를 선언하고 → 제일 첫번째 넣고 방문처리→ { popleft() : 출력→ 뽑은 애의 하위 인자들 중 방문 하지 않은 애들 모두 append → Q가 빌 때까지 반복 }
정의
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다
- 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다
구현
def bfs(graph,visited,start):
queue = deque() #큐를 생성
queue.append(start) #queue에 넣기
visited[start] = True #방문처리하고
while (queue): #큐가 빌때 까지
v = queue.popleft() #꺼내면서
print(v , end =" ")
for itm in graph[v]: #꺼낸 녀석의 하위 Node들 추가
if visited[itm] == False: #방문하지 않았으면
queue.append(itm) #넣고
visited[itm] = True #방문처리
else: pass
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False]*9
bfs(graph,visited,1) #1 2 3 8 7 4 5 6
예제
내 풀이
from collections import deque
def bfs(x_start, y_start): #대각선으로만 움직임 우하향으로 이동한다는 점을 이용
global sol, N, M
queue.append((x_start, y_start))
while (queue): #Queue가 빌때까지
sol += 1 #시작점을 포함하므로
v_x, v_y = queue.popleft() #unpacking
if v_x != N-1 :
if graph[v_x+1][v_y] == 1:
queue.append((v_x+1,v_y))
if v_y != M-1:
if graph[v_x][v_y+1] == 1:
queue.append((v_x,v_y+1))
#input 받아오기
graph = []
sol = 0
queue = deque()
N,M = map(int, input().split())
for _ in range (N):
graph.append(list(map(int,list(input()))))
bfs(0,0)
print(sol)
이코테 풀이
from collections import deque
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 소스코드 구현
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복하기
while queue:
x, y = queue.popleft()
# 현재 위치에서 4가지 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 미로 찾기 공간을 벗어난 경우 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n - 1][m - 1]
# BFS를 수행한 결과 출력
print(bfs(0, 0))
구현은 Queue를 이용하면 된다 → 내 생각은 굳이 재귀 필요 x
from collections import deque
큐를 선언하고 → 제일 첫번째 넣고 방문처리→ { popleft() : 출력→ 뽑은 애의 하위 인자들 중 방문 하지 않은 애들 모두 append → Q가 빌 때까지 반복 }
정의
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다
- 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다
구현
def bfs(graph,visited,start):
queue = deque() #큐를 생성
queue.append(start) #queue에 넣기
visited[start] = True #방문처리하고
while (queue): #큐가 빌때 까지
v = queue.popleft() #꺼내면서
print(v , end =" ")
for itm in graph[v]: #꺼낸 녀석의 하위 Node들 추가
if visited[itm] == False: #방문하지 않았으면
queue.append(itm) #넣고
visited[itm] = True #방문처리
else: pass
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False]*9
bfs(graph,visited,1) #1 2 3 8 7 4 5 6
예제
내 풀이
from collections import deque
def bfs(x_start, y_start): #대각선으로만 움직임 우하향으로 이동한다는 점을 이용
global sol, N, M
queue.append((x_start, y_start))
while (queue): #Queue가 빌때까지
sol += 1 #시작점을 포함하므로
v_x, v_y = queue.popleft() #unpacking
if v_x != N-1 :
if graph[v_x+1][v_y] == 1:
queue.append((v_x+1,v_y))
if v_y != M-1:
if graph[v_x][v_y+1] == 1:
queue.append((v_x,v_y+1))
#input 받아오기
graph = []
sol = 0
queue = deque()
N,M = map(int, input().split())
for _ in range (N):
graph.append(list(map(int,list(input()))))
bfs(0,0)
print(sol)
이코테 풀이
from collections import deque
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 소스코드 구현
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복하기
while queue:
x, y = queue.popleft()
# 현재 위치에서 4가지 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 미로 찾기 공간을 벗어난 경우 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n - 1][m - 1]
# BFS를 수행한 결과 출력
print(bfs(0, 0))
예제 (얼음 개수)