[백준 2644번] 촌수계산 (BFS)

이번 문제부터는 알고리즘 문제를 본격적으로 풀어보려고 합니다.

알고리즘 문제 중에서도 크게 두 가지(DFT, BFS)를 살펴보려고 하는데, 두 가지 방법 모두 적용하여 문제를 접근하며 공부할 예정입니다.

 

우선, 알고리즘 문제부터 입력으로 들어오는 수가 많아질 것이기 때문에 input.txt 파일을 만들어서 직접 관리하려고 합니다.

import sys

sys.stdin = open('input.txt')

[ input.txt 파일을 불러오는 코드 ]

 

첫번째로 dfs 풀이법입니다.

dfs는 이름 그대로 깊이 우선 탐색 방법을 이용하며, 행렬그래프(graph)를 통해서 문제를 풉니다.

 

graph = [[ ] for i in range(N+1)] --> 2차원 빈행렬을 만들어줍니다. 이 문제에서는 두 숫자간의 연결을 직접 정의해줄 예정이므로 빈행렬을 만들어줍니다. 0 by 0은 이용하지 않을 예정이므로 N+1까지의 index를 가지는 행렬을 만들어줍니다.

 

A = start point, B = end point로 사용할 예정입니다.

 

visited = [0] * (N+1) --> 방문기록을 위해 만든 리스트 타입의 데이터입니다.

 

여기서부터 조금 어려운 내용인데,

연결되어 있는 숫자들끼리를 나타내기 위해 graph 행렬 값을 업데이트하려고 합니다.

graph[1].append(2) --> graph[1] = [2]

graph[2].append(1) --> graph[2] = [1] 

.

.

.

graph[2].append(7) --> graph[2] = [7]

graph[7].append(2) --> graph[7] = [2]

.

.

bfs, dfs 문제에서 연결을 묻는 문제는 보통 양방향으로 값 설정을 해줍니다.

 

import sys
sys.stdin = open('input.txt')

N = int(input())
A, B = map(int, input().split())
m = int(input())
graph = [[] for i in range(N+1)]
visited = [0] * (N+1)
result = []

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

def DFS(v, num):
    num += 1
    visited[v] = 1

    if v == B:
        result.append(num)

    for i in graph[v]:
        if visited[i] == 0:
            DFS(i, num)

DFS(A, 0)

if not len(result):
    print(-1)
else:
    print(result[0]-1)

[ dfs 알고리즘 코드 ]

 

import sys
sys.stdin = open('input.txt', 'r')

def bfs(s, e):
    q = []
    v = [0]*(N+1)

    # 시작 value 넣기
    q.append(s)
    # 시작 방문 값 넣기. 해당 값이 촌수를 의미 (1촌부터 시작)
    v[s] = 1

    # q의 리스트 개수만큼 반복하기
    while q:
        # bfs의 핵심: 맨 첫 값부터 빼낸다.
        c = q.pop(0)

        # 끝의 값(최종도달지점)에 도달하면 촌수 추출(-1)한다.
        if c == e:
            return v[e]-1

        # c와 연결된 번호인 경우 미방문이면 방문!
        for n in adj[c]:
            if v[n] == 0:
                q.append(n)
                print(q)
                v[n] += v[c]+1
    return -1


N = int(input())
S, E = map(int, input().split())
M = int(input())

adj = [[] for _ in range(N+1)]
for _ in range(M):
    p, c = map(int, input().split())
    adj[p].append(c)
    adj[c].append(p)


ans = bfs(S, E)
print(ans)

[ bfs 알고리즘 코드]