Heecheol's blog

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 이용해 하나의 수에서 -1한 값, +1한 값, *2한 값을 각각 조건을 확인해준 후, 큐에 넣고 확인하는 것을 반복해주었다. 100001크기의 배열을 선언해서 구현하였따. 처음에 수빈이가 있는 queue[5]를 0으로 초기화하고, +1, -1, *2한 값들에 대해서 배열의 해당 위치가 -1인지 확인 후에 아니라면 이전 값에 +1을 하여 queue[ta..

문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 풀이 어려웠음. 불은 사방으로 퍼지고, 사람은 주변으로 한 칸씩 움직일 수 있다. 우선, BFS를 이용해 불이 각 칸에 언제 도착하는지 미리 구해놓았따. 이후에, 다시 지훈이에 대해서 BFS를 이용해 각 칸에 도달하는 시간을 계산하였따. 이때, fire 배열에서 해당 위치인 [i][j]의 값을 확인해서 person[i][j]보다 값이 작다면 해당 위치는 지훈이가 갈 수 없는 곳..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 이전의 토마토문제와 유사한 문제이며 dz만 생각해주면 쉽게 풀 수 있다. 마찬가지로 BFS를 돌리기전에 미리 큐에 모든 1짜리 토마토를 넣어준다. 다음으로 큐에서 하나씩 확인하며 dx, dy, dz를 1씩 더한 것 중 조건을 만족하며 tomato[newZ][newX][newY]가 0인 것들에 대해서만 기존의 값에서 1을 추가한 뒤 큐에 [newZ,newX,newY..

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 BFS문제이며, 이전과는 달리 시작점이 하나가 아니라 여러 개인 문제였다. 크게 다를 것 없이 처음에 반복문으로 큐에 시작점들을 미리 넣어놓기만 하면 똑같다. 하루마다 주변 토마토를 익게 하기 때문에 주변 토마토까지의 최소 거리를 계산해주면된다. 이때, 0인 곳에만 토마토가 있으므로 -1이거나 0보다 큰 토마토에 대해서는 계산하지 않아도 된다. 여기서 처음에는 더 멀리 ..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 이전의 그림문제와 비슷하게 풀 수 있는 BFS문제였다. 그림 문제에서와는 달리 removeFirst()를 사용하지 않고 두 개의 배열을 이용해 구현해보았다. 근데 케이스가 적어서 removeFirst()로 해도 통과는 될 것 같다. 위, 아래, 양 옆을 모두 확인하여 1인 경우에만 이전의 값에서 1을 더해준 값을 넣어준 뒤, 마지막에 [n,m]지점의 값을 출력하였따. 이 문제에서는 출발점도 정해져있고, 가능한 모든 지..