www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이번 문제는 경로를 추적해서 출력하는 문제였다. 조금만 생각해보면 금방 알 수 있는데, 현재 위치를 지나가는 배열 a를 만들어서 a[next] = cur 를 담고있다고 가정해보면 a[k] 에는 k에 도착하기 전 가장 마지막 위치가 담겨있을 것이고, a[마지막 위치] 에는 그 위치에 오기 위한 위치가 점진적으로 들어있을 것이다. 그렇다면 구현은 간단하다. 기존 bfs를 통해 최단..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 2와 다르게 3은 cur * 2 지점으로 텔레포트할 때에 시간이 소요되지 않는다. 평범하게 큐로 bfs 할 경우 기존 cur -1, cur + 1을 하면서 K에 도착하게 되면 이후에 cur * 2 를 통해 도착하는 시간보다 더 크지만 이미 방문처리가 되어있으므로 값을 갱신시켜줄 수 없다. 어떻게 접근해야될까? 이 문제는 우선순위 큐를 최소 힙으로 선언한 후 time을 ..

www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 며칠 고민해봤는데 풀이 방법이 안 떠올라서 다른 블로그를 참고해서 풀었다. 두 개 정도의 풀이 방법이 있었는데 하나는 K로 가는 방법의 수를 배열 하나를 더 만들어서 접근하는 방법이고 다른 하나는 큐에서 팝 할 때 방문 체크를 해주는 방식이다. 첫 번째 방법은 시간이 항상 1씩 늘어난다는 것을 이용해서 d[next] == d[cur] + 1 이라면 cnt를 증가시키는 방법이..

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 간단한 1차원 BFS 문제인데 fill 배열로 초기화할 때 1000001으로 초기화해줘야 하는데 1000000으로 초기화해서 계속 틀렸다 ㅜㅜ;; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int f, s, g, u, d,..

www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS를 하면서 회전이 총 몇 번 일어났는지 체크해주면 되는데 처음엔 방향 dir 벡터를 선언하고 그 방향과 다르면 +1 해주는 식으로 접근했다가 더 좋은 풀이가 보여서 참고했다. 결국 일직선으로 얼마나 갈 수 있는지를 확인하는 게 중요한데 BFS로 범위를 체크하는 부분에서 while문을 사용해서 범위가 끝날 때까지 직진하도록 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 기존 벽 부수고 이동하기 문제에선 오직 한 번만 벽을 부술 수 있었지만 2번 문제에선 총 10번까지 벽을 부술 수 있다. 따라서 기존 vis[MAX][MAX][2] 였던 배열을 vis[MAX][MAX][11]로 바꿔서 BFS 할 때 조금만 수정해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2..