문제
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
언뜻 문제만 DFS를 이용해 백트래킹을 해야 하는 문제로 보인다. 하지만 이 문제는 최단 경로를 구하는 일차원 그래프 탐색 문제였다. 오히려 다른 BFS문제들보다 더 심플하다. 방문처리만 조금 신경써준다면 수월하게 해결할 수 있다. 미리 그래프의 크기만큼의 리스트를 선언하거나 집합을 이용해서 O(1) 안에 방문처리를 해줄 수 있도록 하자.
코드
'CS > 알고리즘 문제 풀이' 카테고리의 다른 글
| [백준] 1325 - 효율적인 해킹 [Python(파이썬)] (4) | 2021.06.22 |
|---|---|
| [백준] 1759 - 암호 만들기 [Python(파이썬)] (0) | 2021.06.10 |
| [백준] 7576 - 토마토 [Python(파이썬)] (0) | 2021.05.29 |
| [백준] 2178 - 미로탐색 [Python(파이썬)] (0) | 2021.05.23 |
| [백준] 2667 - 단지번호붙이기 [Python(파이썬)] (0) | 2021.05.23 |
문제
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
풀이
언뜻 문제만 DFS를 이용해 백트래킹을 해야 하는 문제로 보인다. 하지만 이 문제는 최단 경로를 구하는 일차원 그래프 탐색 문제였다. 오히려 다른 BFS문제들보다 더 심플하다. 방문처리만 조금 신경써준다면 수월하게 해결할 수 있다. 미리 그래프의 크기만큼의 리스트를 선언하거나 집합을 이용해서 O(1) 안에 방문처리를 해줄 수 있도록 하자.
코드
'CS > 알고리즘 문제 풀이' 카테고리의 다른 글
| [백준] 1325 - 효율적인 해킹 [Python(파이썬)] (4) | 2021.06.22 |
|---|---|
| [백준] 1759 - 암호 만들기 [Python(파이썬)] (0) | 2021.06.10 |
| [백준] 7576 - 토마토 [Python(파이썬)] (0) | 2021.05.29 |
| [백준] 2178 - 미로탐색 [Python(파이썬)] (0) | 2021.05.23 |
| [백준] 2667 - 단지번호붙이기 [Python(파이썬)] (0) | 2021.05.23 |
