DFS - 촌수계산 [2644번]

2022. 7. 17. 20:432022/BaekJoon_알고리즘

DFS 와 BFS로 풀이해보았다.

 

DFS
def dfs(p, cnt):
    global chk
    if p == c:
        chk = True
        print(cnt)
        return
    
    for i in range(101):
        if graph[p][i] == 1 and visited[i] == False:
            visited[i] = True
            dfs(i, cnt + 1)
            visited[i] = False

n = int(input())
p, c = map(int, input().split())
m = int(input())
graph = [[0]*(101) for _ in range(101)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

visited = [False] * 101
visited[p] = True

chk = False

dfs(p, 0)

if chk == False:
    print(-1)

 

BFS
from collections import deque

def bfs(p):
    global c
    q = deque([p])
    while q:
        x = q.popleft()
        if x == c:
            print(visited[x])
            return 
        
        for y in range(len(graph[x])):
            if graph[x][y] == 1 and not visited[y]:
                q.append(y)
                visited[y] = visited[x]+ 1
                
    print(-1)
    return
                
n = int(input())
p, c = map(int, input().split())
m = int(input())
graph = [[0]*(101) for _ in range(101)]
for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1
    
visited = [0] * 101
bfs(p)

'2022 > BaekJoon_알고리즘' 카테고리의 다른 글

BFS - 스타트링크 [5014번]  (0) 2022.07.18
BFS - 안전영역  (0) 2022.07.18
BFS - 숨바꼭질 [1697번]  (0) 2022.07.15
BFS - 단지번호붙이기 [2667번]  (0) 2022.07.14
BFS - 미로 탐색 [2178번]  (0) 2022.07.14