매일 성장하자!!

문제 3차원 토마토 상자의 모든 토마토가 익는 최소 일수를 구해라. 풀이 2차원과 다른점은 갈수있는 경로가 위, 아래 2개 더 는것 뿐이다. 그 이외에는 다른게없다. 가중치 없는 그래프에서 최소일수이므로 bfs로 풀면 쉽게 풀수있다. 코드 package baekjoon.그래프탐색; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main7569 { static int M, N, H; static int[][][] board; static boolean[][][] visited; static List okTomatoes = new ..

문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 풀이 일단 가중치없는 그래프에서 최단 경로이므로 BFS로 풀어야하는 것은 눈치를 챘다. 그런데,,, 쉽게 풀줄..

문제 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다. 버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다. 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다. 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다. 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다. 두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시..

문제 보드위에는 육지와 바다가있는데 육지에서 육지로만 갈수있고 현재위치에서 상하좌우 밖에움직이지 못한다. 이 보드위에 보물이 두군데 묻혀있는데 보물은 최단거리중 가장 긴 시간이 걸리는 곳에 묻혀있다. 보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오. 풀이 최단거리리라는 것이 무엇인지 문제에 주어져있다. 이 문제를 보고 bfs로 바로 풀어야겠다는 생각이 난들었다. (가중치없는 최단거리이동은 bfs이다.) bfs가 어떤식으로 그래프를 탐색하는지 생각하면 어렵지않게 생각할수있는 문제이다. 보드의 각 위치를 모두 탐색하면서 해당 위치에서 가장 긴시간이 걸리는 육지칸을 찾은 다음, 이 시간과 static 변수인 max중 큰 값을 비교하며 최신화하며 ..