[백준] 2644번 : 촌수계산[Python]

문제 : https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

풀이 :

두가지 방법(BFS, DFS)으로 풀이를 진행하였음

 

첫번째 방법(BFS)

1. 노드 저장할 graph 리스트 초기화

2. 방문 여부 판별 + 몇촌인지 저장할 visited 리스트 초기화

3. graph에 노드 저장

4. bfs 진행

5. 정답 출력

visited[target2]가 0일 경우 촌수 확인 할 수 없는 경우이므로 -1 출력

visited[target2]가 0이 아닐 경우 visited[target2] 출력

 

두번째 방법(DFS)

1. 노드 저장할 graph 리스트 초기화

2. 방문 여부 판별힐 visited 리스트 초기화

3. graph에 노드 저장

4. 촌수 있는지 없는지 확인 하기 위한 chk 변수 초기화

5. dfs 진행

6. 정답 출력

chk가 False일 경우 촌수 확인 할 수 없는 경우이므로 answer = -1

chk가 True일 경우 answer 출력

 

 

코드 :

첫번째 방법(BFS)

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
target1, target2 = map(int,input().split())
m = int(input())

graph = [[] for _ in range(n+1)]        # 노드 저장할 graph 리스트 초기화
visited = [0] * (n+1)                   # 방문 여부 판별 + 몇촌인지 저장할 visited 리스트 초기화
for i in range(m):                      # graph에 노드 저장
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

def bfs(start):                     
    q = deque()
    q.append(start)
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = visited[v] + 1
                q.append(i)
bfs(target1)
if visited[target2] == 0:   # visited[target2] == 0이면 촌수를 계산할 수 없는 경우이므로 -1출력
    print(-1)
else:                                   
    print(visited[target2])

 

두번째 방법(DFS)

import sys
input = sys.stdin.readline
n = int(input())
target1, target2 = map(int,input().split())
m = int(input())

graph = [[] for _ in range(n+1)]        # 노드 저장할 graph 리스트 초기화
visited = [False] * (n+1)               # 방문 여부 판별할 visited 리스트 초기화
for i in range(m):                      # graph에 노드 저장
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
answer = 1                              
chk = False                             # 촌수 있는지 없는지 판별하기 위한 변수
def dfs(start,ans):                     
    global answer
    global chk 
    if chk == True:                     # 촌수 확인 되면 dfs 종료
        return
    visited[start] = True               
    for i in graph[start]:              
        if i == target2:                
            chk = True
            answer = ans
        if not visited[i]:              
            dfs(i,ans+1)

dfs(target1,answer)
if chk == False:
    answer = -1

print(answer)