[Python/파이썬][🥈2] 백준 알고리즘 2644 - 촌수계산

📖[Python/파이썬][🥈2] 백준 알고리즘 2644 - 촌수계산

📜문제

---

DFS(깊이우선탐색)

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
#Stack #스택 #재귀 #순환 #무한루프탈출 #Back-Tracking

BFS(넓이우선탐색)

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
#Queue #큐

---

📕풀이방향

DFS알고리즘

n,s(start),e(end),m,노드들을 저장하고, dfs()함수를 통해 start==end일 때, dep을 출력하자

BFS알고리즘

n,s(start),e(end),m,노드들을 저장하고, bfs()함수를 통해 res에 촌수를 저장해가면서
큐가 비었을 때 res를 출력하자

---

📝알고리즘 구현순서

DFS알고리즘

1. n,s(start),e(end),m,노드들을 MAP으로 인덱싱하여 저장, visited(list)를 1e9로 초기화하여
   dfs()에서 start == end일 때, visited[end]값을 출력하자

❓ visited를 1e9로 초기화하는 이유

  dfs()를 호출할 때마다 dep를 증가시켜서 파라미터로 넘길껀데,
  visited[end]에 저장된 값과 dep를 비교하여 
  더 작은 값을 최종 visited[end]에 넣어 반환할꺼니까!

BFS알고리즘

1. n,s(start),e(end),m,노드들을 MAP으로 인덱싱하여 저장, visited(list)를 False로, res(list)를 초기화하자
2. bfs()에 start값을 큐에 넣어, 하나씩 꺼내면서 방문한적이 없으면 res를 증가시키자
3. bfs()함수 종료 후 res[end] > 0이면 방문한적이 있다는 뜻이므로 호출,
   아니면 "-1"을 출력하자

---

💻결과코드

DFS알고리즘

import sys
input = sys.stdin.readline

n = int(input().rstrip())
start,end = map(int, input().split())
m = int(input().rstrip())
node = [map(int, input().split())for _ in range(m)]
visited = [1e9]*(n+1)

#인덱싱하기
amap = [[] for _ in range(n+1)]
for x,y in node:
    amap[x].append(y)
    amap[y].append(x)

#DFS
def dfs(start, end, amap, dep):
    if start == end:
        visited[end] = min(visited[end],dep)
        return

    for i in amap[start]:
    	#방문한 적이 없으면 방문하여 dep 저장
        if visited[i] > dep:
            visited[i] = dep
            dfs(i, end, amap, dep+1)

dfs(start, end, amap, 1)

#visited[end]값이 1e9이면 방문한 적이 없다는 뜻이니까
if visited[end] == 1e9:
    print(-1)
else:
    print(visited[end])

---

BFS알고리즘

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
start, end = map(int, input().split())
m = int(input())
node = [list(map(int, input().split())) for _ in range(m)]
visited = [False]*(n+1)
res = [0]*(n+1)

#인덱싱하기
rel = [[] for _ in range(n+1)]
for u,v in node:
    rel[u].append(v)
    rel[v].append(u)

#BFS
def bfs(start):
    queue = deque()
    queue.append(start)
    visited[start] = True
	
    #큐가 빌 때까지 실행
    while queue:
    	#제일 먼저 들어온 값부터 검사
        v = queue.popleft()
        
        for i in rel[v]:
            if not visited[i]:
                queue.append(i)
                #함수 밖에 있는 res에 현재노드(v)와의 촌수를 저장
                res[i] = res[v]+1
                visited[i] = True

bfs(start)
#res[end]값이 0이면 방문한 적이 없다는 뜻이니까
if res[end] > 0:
    print(res[end])
else:
    print(-1)

---

📚정리

내 포스팅 : [Python/파이썬][🥈2] 백준 알고리즘 1260 - DFS와 BFS
1. DFS와 BFS중 선택, 인덱싱/인접행렬중 선택이 관건인 것 같다.
(위 포스팅에서 다뤘듯이 방법이 너무 다양해서 설계 시 방법을 선택하는 것이 관건)