1260 2 [백준,Python]1697번 숨바꼭질(BFS) 백준 1697번: 숨바꼭질 문제를 리뷰하는 시간을 가져보겠습니다. 문제를 요약하면, -N과K 두 수를 입력 받아 N이 K에 도달하는 최단 시간을 구하는 문제이고, N은 1초에 +1,-1,*2방법을 통해 이동할 수 있습니다. (자세한 문제 설명은 https://www.acmicpc.net/problem/1697를 참고하시면 됩니다.) 먼저, 이 문제는 BFS로 푸는 문제이며, DFS와의 차이에 대해서 간략하게 설명드리겠습니다. DFS는 탐색하면서 depth가 증가할 때 마다, 기준점을 바꾸고 재귀를 써서 탐색을 진행하게 되는데, 이 문제를 그렇게 풀 경우 무한 루프에 빠지므로 BFS로 푸는 방식을 이용해 탐색을 진행하도록 구현하였습니다. DFS로 풀지 않고 BFS로 푼다의 가장 큰 특징은 for문 또는 w.. 2020. 8. 15. [백준,Python]1260번 DFS와 BFS(DFS&BFS) 오늘 리뷰하는 문제는 DFS와 BFS의 기초를 공부하기에 좋은 문제라고 생각되는 문제입니다. 백준 1260번 문제를 Python으로 구현해보았습니다. 먼저, 간략하게 문제를 소개하자면, Input으로 정점 개수 N, 간선 개수 M, 시작 정점 V를 입력받고, M만큼 간선 들을 또 입력받고 Output으로 DFS와 BFS의 결과를 출력하는 문제입니다. (자세한 문제 설명은 https://www.acmicpc.net/problem/1260로 확인하시면 됩니다.) 일단 간단하게 개념을 설명하자면, DFS는 깊이 우선 탐색으로 그래프가 있을 때 방문한 점에서 길이 있으면 길이 없을 때까지 계속 방문하고 없으면 처음 루트에서 다시 탐색을 진행하는 알고리즘이고, BFS는 너비 우선 탐색으로 시작 루트 기준으로 가능.. 2020. 8. 11. 이전 1 다음
