BOJ 7569 - 토마토
토마토 문제는 두 개가 있는데, 각각 2차원 bfs와 3차원 bfs 문제다.
사실 푸는 법은 거의 차이 없는데 3차원이 분위기상 더 어려워보이는 감이 있고.. 그래서 미뤄뒀다가 오늘 풀었다.
한창 알고리즘 강의 들으러 다닐 때 2차원 토마토 풀었었는데, 그 때 비효율적으로 풀어서 실행 시간 많이 나왔던거에 비하면 이번에는 깔끔하게 풀어서 만족!
접근 방법
2차원 bfs나 dfs 문제 풀 때는, 네 방향 조작을 위해서 다음과 같은 배열을 만들어놓는다.
int[] dX = {-1, 0, 0, 1};
int[] dY = {0, -1, 1, 0};
사람 취향마다 다르겠지만 나 같은 경우는 각각 상,좌,우,하로 넣어놓고 조작하고 있다.
3차원 bfs는 여기에 Z 배열 및 case 두개를 추가하면 된다.
int[] dX = {-1, 0, 0, 1, 0, 0};
int[] dY = {0, -1, 1, 0, 0, 0};
int[] dZ = {0, 0, 0, 0, 1, -1};
추가된 케이스는 한층 위, 한층 아래이다.
이 문제에서 bfs를 전개 시키는 방법은 여러 가지가 있겠지만, 처음에 입력 받으면서 값이 1인 경우 큐에 미리 넣어놓고 그걸 기반으로 bfs를 하면 된다.
(예전에 2차원 토마토 문제 풀 때 이렇게 안하고 조금 이상하게 했다가 많이 힘들게 풀었던 기억)