알고리즘 (2) 썸네일형 리스트형 [BOJ] 백준 1697 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해결사항: 수빈이는 현재 위치에서 3가지로 이동할 수 있다. 위 3가지 이동을 하나의 그래프의 신장으로 보았을때 그래프를 신장해가며 너비 우선 탐색을 진행하다보면 동생의 위치를 알 수 있다. 문제를 해결하면서 첫번째에 봉착한 문제는 "몇 초"가 걸리는지를 함께 아는것이 중요하다. 제시된 예제 입력을 통해 알아보자. 예제 입력: 5 17 예제 출력: 4 가장 먼저 든 생각.. [BOJ] 백준 1004 어린왕자 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 해결사항: 만약에 이 문제가 최단거리를 요구했다면 더 어려웠을 것이다. 하지만 단순히 요구하는 것은 행성계 진입/이탈 의 횟수를 최소화 하는 경로를 찾는 것. 즉, 경로가 아무리 길어져도 행성계 진입/이탈 횟수만 적다면 된다는 뜻이다. 결국 이 문제는 출발점/도착점이 각각 몇개의 행성계에 속해있는가를 알아보는 것이다. 1. 모든 행성계를 순회하며, 출발점/도착점이 행성계 안에 존재하.. 이전 1 다음
