[Gold5] No.07576 토마토

토마토

No.07576 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

문제풀이

오랜만에 알고리즘이다. 주말동안 코딩테스트를 보느라 알고리즘을 주구장창 풀어서 너무 지친상태였다.

다시 마음잡고 알고리즘을 시작해 보자. ;D

이제 문제만 봐도 알것 같다! 먼저 좌표와 2차배열 문제는 그래프 탐색 알고리즘이라고 봐도 무방하다.

해당 문제를 풀기 위해서는 몇가지 특징을 잡아 풀어주면 된다.

• 해당 문제는 bfs를 이용한다.

문제에서 주어진 토마토들이 익는 방법은, 이미 익은 다수의 토마토 옆에 있을경우에만 익기 때문에 동시 다발적으로 처리가 필요하므로, bfs를 이용한다. 또한, 토마토가 익은 시작점은 무조건 하나가 아닌

(0,0)의 좌표와 (3,5)의 좌표의 토마토부터 동시에 시작해야 하므로, 아래의 코드와 같이 모두 탐색을 진행 한 후, 익은 토마토가 있는 좌표를 Queue에 넣어준 뒤 bfs를 진행한다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (tomatoBox[i][j] == 1){
            queue.offer(new Node(i, j));
        }
    }
}
bfs();

• 익은 토마토의 좌표를 기준으로 상하좌우를 탐색한다.

기준점에서 상하좌우의 값을 변동 시킬 경우는 아래의 코드를 이용한다.

static int[] dirX = {0, 0, -1, 1};
static int[] dirY = {1, -1, 0, 0};

...
 for (int i = 0; i < 4; i++) {
    int ny = node.y + dirY[i];
    int nx = node.x + dirX[i];

    if (ny < 0 || nx < 0 || nx >= m || ny >= n || tomatoBox[ny][nx] != 0)
        continue;

    tomatoBox[ny][nx] = tomatoBox[node.y][node.x] + 1;
    queue.offer(new Node(ny, nx));
}

dirX와 dirY의 좌표를 기준점 node.y, node.x의 좌표에 상하좌우 각각 모두 더해 좌표 밖을 튕겨나가거나 특별한 조건을 벗어나지 않은 이상 탐색 및 값을 변경 해준다.

• 마지막으로, 토마토가 모두 익은 일 수 를 구한다.

결국 토마토가 익었냐 설익었냐는 중요하지 않다. 해당 문제는 좌표의 모든 토마토가 익는데 걸리는 시간 혹은 익을 수 있느냐에 대해 반환하는 문제이다.

날짜 변수를 생성해 bfs 밖에서 +1하거나, 익은 토마토를 판별하는데 +1 하는 로직을 넣을 수는 없다.

tomatoBox[ny][nx] = tomatoBox[node.y][node.x] + 1;

해당 로직을 이용해 토마토가 차례로 익을수록 1을 더해서 값을 치환해준다. 그러면 최종 결과물은 다음과 같다.

풀이소스