-
2644. [Python]촌수계산Python_알고리즘/Silver II 2023. 9. 4. 19:28
1. 문제
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- DFS(깊이 우선 탐색)
3. 파이썬 코드
import sys # 많은 인풋 처리 input = sys.stdin.readline # DFS 함수 def DFS(start): # 시작 위치 1로 방문처리 visited[start] = 1 global cnt global end # matrix로 접근 for i in range(N+1): # matrix 값이 1인 경우 if matrix[start][i] == 1: # 방문하지 않았다면 if visited[i] == 0: # i 값이 목표값과 같은 경우 if i == end: # cnt 출력 후 실행 종료 print(cnt) exit() # 외의 경우 else: # cnt 값 증가(촌수 계산) cnt += 1 # 방문처리에 이전값 + 1 visited[i] = visited[start] + 1 # 재귀 실행 DFS(i) # 방문처리 취소 visited[i] = 0 # cnt 값 다시 감소 cnt -= 1 N = int(input()) start, end = map(int,input().split()) # 부모 자식간의 관계 수 m = int(input()) # martix 생성 matrix = [ [0]*(N+1) for _ in range(N+1) ] # visited 생성 visited = [0] * (N+1) for _ in range(m): # A,B 인풋 값 추가 A,B = map(int,input().split()) matrix[A][B] = 1 matrix[B][A] = 1 # 촌수 계산 변수 cnt = 1 # 값이 없는걸 체크할 리스트 ans = [] DFS(start) # DFS 함수를 통해서 값을 못찾았을 경우 -1 출력 if len(ans) == 0: print(-1)
4. 문제를 풀고난 후 생각
- 이런 어느 정도 깊이까지 갔는지 체크하는 문제의 경우는 BFS로 푸는 것이 좀 쉽게 접근이 가능한 문제이다.
- DFS로 풀어보고 싶어서 생각해서 구현을 진행했고, 촌수를 cnt += 1로 계산을 해주며 재귀, 백트래킹을 적용해서 촌수의 계산을 진행했다.
- 원하는 촌수를 찾았을 경우 exit() 구문을 사용해서 촌수를 출력 후 코드를 종료시켰고, 만약 DFS 함수가 끝난 경우 ans라는 빈 리스트를 생성하여 촌수를 못찾았다고 가정하고 -1 을 출력하는 식으로 해결했다.
- 문제를 풀면서 BFS로 접근을 했으면 쉽게 정답을 찾았을 것이라 생각이 들어서 다음에 BFS로 접근해볼 예정이다.
5. 문제를 푸는데 도움이 되는 지식
- 깊이 우선 탐색
- 너비 우선 탐색
'Python_알고리즘 > Silver II' 카테고리의 다른 글
17086. [Python]아기 상어2 (0) 2023.09.26 18870. [Python]좌표 압축 (0) 2023.09.04 5002. [Python]도어맨 (1) 2023.08.27 1012. [Python]유기농 배추 (0) 2023.08.19 1564. [Python]팩토리얼5 (0) 2023.08.13