Heecheol's blog

문제 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]지점의 값을 출력하였따. 이 문제에서는 출발점도 정해져있고, 가능한 모든 지..

문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 BFS로 해결할 수 있는 문제였고, 익숙하지가 않아서 어려웠다. 반복문을 통해 보드를 하나씩 이동하며 방문하지 않은(visited가 false) 자리이고, paper[i][j]가 1인 경우에 BFS를 통해 그림을 확인하였다. BFS를 수행하는 과정은 다음과 같다. 우선, 큐에 해당 위치인 [i][j]를 넣어준다. 다음으로 [i][j]를 방문했으므로 visited[i][j]를 true로 바꿔준..