[python] 백준 - 2644. 촌수계산

문제 해결

1. 노드간의 최단거리를 구하는 그래프에 관한 기본적인 문제이다.

2. 먼저 주어진 부모자식들 간의 관계를 가지고 인접리스트를 만든다.

3. visit 배열을 만들어 방문 여부를 가지고 DFS 재귀함수를 진행한다.

 (1) 현재 노드에 인접한 노드를 for문을 통해 뽑아주고,

 (2) 만약 인접한 노드가 아직 방문하지 않은 상태라면, 그 노드로 이동 - 재귀

 (3) 이동한 노드가 구해야하는 노드라면 방문한 노드들의 갯수를 세어주고 결론을 도출.

 

-> 쉬운 문제라고 생각했는데 한참동안 '틀렸습니다'를 얻었다. 이번에도 역시 이웃님의 도움을 받았다.

 `촌수관계를 나타내지 못하면 -1을 출력해라`....... 문제를 잘 읽어보는 습관을 들여야겠다.

소스 코드

n = int(input())
a, b = map(int, input().split())
m = int(input())


def dfs(vertex):
    global result
    if result > 0:  # a -> b 까지 도착했으므로 result 의 값이 변했다. 결과가 나왔기에 다른 모든 함수를 종료
        return

    if vertex == b:  # a -> b 까지 도착
        result = visit.count(True) - 1  # 촌수는 배열의 길이에서 -1 | ex) 나-아빠-할아버지 : 2촌
        return

    for neighbor in adj[vertex]:  # 현재노드와 인접한 노드 중에서
        if visit[neighbor] is False:  # 방문하지 않은 노드가 있으면
            visit[neighbor] = True  # 방문
            dfs(neighbor)  # 노드를 들고 다시 dfs
            visit[neighbor] = False  # 원하는 값에 도달하지 못하고 나오면 방문 목록에서 제거

    return


# 그래프 문제의 기본!! 인접xx 중 하나 작성하기, 여기서는 인접리스트 사용
adj = [[] for _ in range(n+1)]
for _ in range(m):  # 방향이 없는 그래프이므로 s->e, e->s 둘다 넣어준다.
    s, e = map(int, input().split())
    adj[s].append(e)
    adj[e].append(s)

result = -1  # 촌수를 따질 수없을 때는 -1 이므로 -1로 두고 시작
visit = [False]*(n+1)  # 방문했는지 아닌지를 확인하기 위해 visit 배열 사용 ( 나중에 이 배열의 길이로 촌수를 계산 )
visit[a] = True  # a 를 시작으로 두고
dfs(a)  # dfs 함수시작!

print(result)

출처 : BACKJOON ONLINE JUDGE

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

2644번: 촌수계산