그래프 탐색 알고리즘
- 그래프의 모든 꼭짓점을 방문하는 알고리즘을 의미
- 둘의 차이는 노드 방문 순서
깊이 우선 탐색 (DFS)
- 깊이를 우선으로 탐색하는 알고리즘 - 루트 노드(또는 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식 - 최대한 깊이 내려간 뒤, 더 이상 내려갈 곳이 없으면 옆으로 이동하는 방식 - 모든 노드를 방문하고자 할 때 사용되는 방법 - **스택**이나 **재귀함수**를 이용하여 구현 - BFS보다 느리다
- 경로의 특징을 저장 해둬야 하는 문제
- 예를 들어, 경로에 같은 숫자가 있으면 안 된다, 각각의 경로마다 특징을 저장해둬야 한다 등
- 검색 대상 그래프 큰 문제
너비 우선 탐색 (BFS)
- 너비를 깊이보다 우선으로 탐색하는 알고리즘 - 최대한 옆으로 넓게 이동한 뒤 더 이상 옆으로 갈 수 없으면 아래로 이동하는 방식 - 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문할 수 있음 - 최단 경로를 찾고자 할 때 사용 - 큐를 이용하여 구현
- 최단거리 구해야 하는 문제
- 가까운 곳부터 찾기 때문에 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리
분석
- 정점의 개수, 간선의 개수, 정점의 번호가 주어졌을 때 그래프를 DFS와 BFS로 탐색한 결과 출력
- 정점 번호가 작은 것을 먼저 방문
- 더이상 방문을 못하는 경우 종료
입력
- N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점의 번호
- 다음 M개의 줄: 간선이 연결하는 두 정점의 번호
출력
- DFS를 수행한 결과
- BFS를 수행한 결과
풀이
N, M, V = map(int, input().split())
#행렬 만들기
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
a, b = map(int, input().split())
graph[a][b] = graph[b][a] = 1
#방문 리스트 행렬
visited1 = [0]*(N+1)
visited2 = visited1.copy()
# dfs
def dfs(V):
visited1[V] = 1 # 방문처리
print(V, end=' ')
for i in range(1, N+1):
# 노드 V와 연결되어 있고, 방문하지 않은 노드 찾기
if graph[V][i] == 1 and visited1[i] == 0:
dfs(i)
# bfs
def bfs(V):
queue = [V] # 시작 노드 큐에 추가
visited2[V] = 1 # 방문처리
while queue: # 큐가 빈다 -> 방문할 노드가 없다
V = queue.pop(0) # 방문 노드 제거
print(V, end = ' ')
for i in range(1, N+1):
# 노드 V와 연결되어 있고, 방문하지 않은 노드 찾기
if (visited2[i] == 0 and graph[V][i] == 1):
queue.append(i)
visited2[i] = 1
dfs(V)
print()
bfs(V)문제
- 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸림
- 1번 컴퓨터가 웜 바이러스에 걸렸다 (고정) -> 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력
입력
- A: 컴퓨터의 수 (100 이하인 양의 정수)
- B: 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수
- B만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터 번호 쌍
출력
- 웜 바이러스에 걸리게 되는 컴퓨터의 수 출력
풀이
- 모든 컴퓨터를 찾아야 하기 때문에 DFS 활용
N = int(input()) # 컴퓨터의 수
M = int(input()) # 컴퓨터 쌍의 수
A = [[0] *(N+1) for _ in range(N+1)]
# 행렬 만들기
for i in range(M):
a, b = map(int, input().split())
A[a][b] = A[b][a] = 1
visited = [0] * (N+1)
answer = []
def dfs(V):
visited[V] = 1
answer.append(V)
for i in range(N+1):
if visited[i] == 0 and A[V][i] == 1:
dfs(i)
dfs(1)
print(len(answer)-1)- 간단한 dfs 문제, 구현만 하면 된다
- answer에 정점들을 넣어주고 길이를 출력해주었다. 1은 포함하면 안 되니 마지막 -1까지
문제
- 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타냄
- 연결된 집의 모임인 단지를 구하기
- 연결되었다 -> 어떤 집이 좌우, 아래위로 다른 집이 있는 경우 (대각선은 X)
풀이
- 갑자기 생각이 났는데 예전에 dfs 풀 때 dx, dy해서 방향 설정해놓고 돌렸던 기억이 난다... 그건가
N = int(input()) # 지도의 크기
graph = []
for i in range(N):
a = list(map(int, input().rstrip()))
graph.append(a)
dx = [0,0,-1,1]
dy = [1,-1,0,0]
count = 0
result = []
def dfs(x, y):
global count
if x < 0 or x >= N or y < 0 or y >= N:
return
if graph[x][y] == 1:
count += 1
graph[x][y] = 0 # 방문처리
for j in range(4):
nx = dx[j] + x
ny = dy[j] + y
dfs(nx,ny)
for i in range(N):
for j in range(N):
if graph[i][j] == 1:
dfs(i,j)
result.append(count)
count = 0
result.sort()
print(len(result))
for i in result:
print(i)- 마지막에 정렬 안 해서 한 번 틀렸다... 문제를 잘 읽자!!!
- 상하좌우 확인을 위해 dx, dy에 값을 넣어주고 반복문을 돌리면서 탐색
- 정사각형을 넘는 경우 방지 처리 먼저 해주고, 1인 경우 개수를 세주고 (단지에 집이 있는 곳 수) 방문 처리를 해준다. 상하좌우 돌면서 있는 집을 다 세준다!
- 그래프가 1인 경우(집이 있는 경우)부터 탐색을 시작하여 개수를 세준다 -> 단지 찾기
문제
- 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 익음
- 인접한 곳: 상하좌우에 있는 토마토 - 며칠이 지나면 다 익게 되는지 날짜 구하기
입력
- M: 상자의 가로 칸 수, N: 상자의 세로 칸 수
- 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어짐
- 1은 익은 토마토, 0은 익지 않은 토마토, -1은 토마토가 없음
출력
- 토마토가 모두 익을 때까지의 최소 날짜
- 모두 익지 못하는 상황이면 -1 출력
- 저장될 때부터 모두 익어있는 상태이면 0을 출력
풀이
- 최단거리니까 bfs 활용해보자
- 마지막 값이 0이면 -1 출력
- 0이 없을 때까지?
from collections import deque
M, N = map(int, input().split())
graph = []
for i in range(N):
g = list(map(int, input().split()))
graph.append(g)
dx = [0,0,-1,1]
dy = [1,-1,0,0]
answer = 0
queue = deque([])
for i in range(N):
for j in range(M):
if graph[i][j] == 1:
queue.append([i,j])
def bfs():
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
graph[nx][ny] = graph[x][y] + 1
queue.append([nx,ny])
bfs()
for i in graph:
for j in i:
if j == 0:
print(-1)
exit(0)
answer = max(answer, max(i))
print(answer-1)- 상하좌우 탐색
- 모든 토마토를 확인하고, 익지 않은 친구가 있다면 -1을 출력
- 최대값을 최소 일수로 출력
문제
- 주어진 항공권을 모두 이용하여 여행경로를 짬
- 항상 "ICN"에서 출발
- 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 return
- tickets의 각 행 [a,b]는 a에서 b로 가는 항공권을 의미
입력
- tickets: 항공권 정보가 담긴 2차원 배열
출력
- 방문하는 공항 경로를 배열에 담아 return
풀이
- 모든 경우를 봐야 하므로 dfs?
- "ICN"에서 시작하는 것과 알파벳이 빠른 순, 그리고 계속 이어지게 가는 게 중요하겠다
틀린 풀이
def solution(tickets):
a = len(tickets)
visited = [0] * a
tickets.sort(key=lambda x: (x[0], x[1]))
print(tickets)
answer = []
def dfs(airport):
answer.append(airport)
for i, (j,k) in enumerate(tickets):
if j == airport and visited[i] == 0:
visited[i] = 1
dfs(k)
dfs("ICN")
return answer
#print(solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]))
# ["ICN", "JFK", "HND", "IAD"]
#print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]))
# ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
print(solution([["ICN", "BBB"], ["BBB", "ICN"], ["ICN", "AAA"]]))
# ["ICN", "BBB", "ICN", "AAA"]이게 첫 풀이었는데 순서대로는 맞지만, AAA는 이어질 곳이 없다 이 부분을 빼먹었다...
꾸준히 공부하기