[백준] python 파이썬 - 촌수계산

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

2644번: 촌수계산

백준 2644번 : 촌수계산

 

1-1. DFS - 실패

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(3000)

n = int(input())
a,b = map(int, input().split())
m = int(input())
li = [[]for _ in range(n+1)]
visited = [False] * (n+1)

def dfs(num) :
    global res
    visited[num] = True
    
    for i in li[num] :
        if not visited[i] :
            res+=1
            dfs(i)
            
res = 0
for _ in range(m) :
    i,j = map(int, input().split())
    li[i].append(j)
    li[j].append(i)
    
dfs(a)
if res == 0 : print(-1)
else : print(res)

DFS로 풀때에는 이렇게 먼저 풀었는데, 답이 죽어도 원하는 값이 안 나오길래 검색해봤다.. 

 

 

1-2. DFS - 실패(성공같은데...) 

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(3000)

n = int(input())
a,b = map(int, input().split())
m = int(input())
li = [[]for _ in range(n+1)]
visited = [False] * (n+1)

def dfs(num, cnt) :
    global res
    
    visited[num] = True
    if num == b:
        res = cnt
        return
    
    for i in li[num] :
        if not visited[i] :
            
            print(i, visited[i], cnt)
            dfs(i, cnt+1)
            
    
res = 0
for _ in range(m) :
    i,j = map(int, input().split())
    li[i].append(j)
    li[j].append(i)
    
dfs(a, 0)
if res == 0 : print(-1)
else : print(res)

나랑 가장 흡사하게 푼 사람을 찾아내서 나랑 다른 점을 찾아봤는데, cnt의 차이였다.

사실 이렇게 봐도 뭐가 큰 차이인지 잘 모르겠는 것... 

아무튼 이렇게 해서? 제출했는데?? 질문하기에 있는 반례도 다 맞았다고 뜨는데 자꾸 틀렸다고 뜸.

이유를 도통 생각해도 모르겠음....... 그래서 결국 DFS 포기하고 다시 BFS로 풀기로 했따

 

 

2. BFS

# -*- coding: utf-8 -*-
import sys
from collections import deque
# sys.setrecursionlimit(3000)

n = int(input())
a,b = map(int, input().split())
m = int(input())
li = [[]for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m) :
    i, j = map(int, input().split())
    li[i].append(j)
    li[j].append(i)

def bfs(num) :
    queue.append(num)
    
    while queue :
        f = queue.popleft()
       
        for v in li[f] :
            if not visited[v] :
                visited[v] = visited[f] + True
                queue.append(v)
    return -1
    
   
queue = deque()
bfs(a)


if visited[b] == False : print(-1)
else: print(visited[b])

다시 푼 최종의 최종.. 

사실 DFS, BFS는 그래프만 정해져있다면 함수 내에 코드는 거의 비슷한데 어떤 값을 return 할 거냐, 또는 어떤 값을 찾길 원하느냐에 따라서 메인 코드가 바뀌는 것 같다. 그것만 잘 찾아내면 쉽게 풀 수 있을 것 같은데 그게 어려운 게 문제^^.. 

 

처음에는 최단거리니까 당연히 BFS로 풀어야지! 하고 손대다가 문제를 이해할 수록 저번에 풀었던 순열 사이클이랑 문제가 비슷한 거 같아서 DFS로 푸니까 골머리 아파져서 돌고 돌아 다시 BFS로...

DFS BFS 너무 어려워요