백준 Q5558 치즈

in Algorithm on baekjoon


문제

문제 원문: https://www.acmicpc.net/problem/5558

어떤 맵이 H * W 직사각형으로 있고 그 안에 둥지, 치즈, 장애물, 빈곳이 존재한다. 이 맵에서 쥐가 둥지에서부터 시작하여 1부터 N까지 치즈를 먹으려한다.
쥐의 첫 체력은 1이며 치즈를 1개 먹을때마다 체력 1이 증가한다. 쥐가 치즈먹는 시간은 무시한다. 쥐의 체력보다 초과하는 치즈는 먹을 수 없다.
쥐는 동서남북으로 이동하며, 이동하는데 걸리는 시간은 1분이다. 물론 장애물에는 갈 수 없으며, 치즈가 있는 곳을 방문시 안 먹고 갈 수 있다.
여기서 쥐가 모든 치즈를 먹는 최단시간을 구하라.

입력

1행: H, W, N (1 ≤ H ≤ 1000, 1 ≤ W ≤ 1000, 1 ≤ N ≤ 9)
2행~H+1행: H*W사이즈의 맵 (S:시작점/X:장애물/.:빈곳/1~N:치즈)
(여기서 쥐는 모든 치즈를 먹을 수 있다는 보장을 받는다.)

출력

쥐가 S에서 출발하여 모든 치즈 먹기까지 걸리는 최단 시간

풀이

이전에 푼 Q16928과 비슷한 문제이다.

맵을 입력 받으면 시작점 S와 목표점 1부터 N까지 알 수 있다. 여기서 쥐는 1부터 N까지 순서대로 먹어야 하므로 먹을 때마다 시작점과 도착점이 달라진다는 것을 알 수 있을 것이다.
즉, 이는 시작점부터 1까지, 1부터 2까지, 2부터 3까지해서 n-1부터 n까지 가는 최소 거리를 누적한 값을 구하는 것이 목표인 것이다.

위 정보들을 요약을 하면…

  • 쥐는 S에서 1까지, 1부터 2까지 … 해서 N-1부터 N까지 순서대로 이동한다.
  • 각구간의 최소 거리를 누적한 것이 이 문제의 목표이다.

이제 풀어본다면 우선 맵을 입력 받아 시작점부터 알아본다.

char[][] map = new char[h][w];
int startX = -1;
int startY = -1;

// 맵 저장
for(int i = 0; i < h; i++){
    char[] mapLine = br.readLine().toCharArray();
    for(int j = 0; j < w; j++){
        map[i][j] = mapLine[j];

        //스타트 지점 저장
        if(map[i][j] == 'S'){
            startX = i;
            startY = j;
        }
    }
}

그렇다면 최소 거리 찾는 횟수는 최대 N번일 것이며, 각 회수마다 시작점과 도착점이 달라지며, 최초 시작점은 ‘S’ 구역부터이다.
이후 최초 시작점을 기준으로 동서남북 4방향 순으로 너비 탐색을 진행한다. 여기서 동서남북 4방향이란 현재 원점에서 x축으로 1 또는 -1, y축으로 1 또는 -1로 움직이는 것으로 설계를 할 수 있다.

// dx, dy의 인덱스에 따라 다음 방향을 결정짓는다.
private static final int[] dx = {0, 1, 0, -1};
private static final int[] dy = {1, 0, -1, 0};

탐색을 진행하면서 방문여부를 체크를 하여 최소 방문 횟수를 각 지점마다 저장을 해준다. 여기서 너비 탐색하는 방법은 Queue 자료구조를 이용하는 것이다. 이용하는 방법은 다음과 같다.

  1. 시작점을 Queue에 넣는다.
  2. Queue의 HEAD부분을 뺀 것을 기준으로 모든 경우의 수에 해당하는 것에 대해서 유효성을 확인한 후 Queue에 넣어준다.
  3. 2번 과정을 Queue가 빌 때까지 진행한다.

이 과정을 이 문제에 대입하면…

  1. 시작점을 Queue에 넣는다.
  2. Queue의 HEAD부분을 뺀 지점의 4방향에 해당하는 지점의 유효성을 확인한다.
  3. 이 문제에서 유효성은 도착지점이 맵 내에 있는지, 장애물이 아닌지, 방문한 적이 있는지이다.
  4. 해당 도착지점의 유효성 검사가 통과되는 그 지점에 최소 방문 횟수를 표시하고 Queue에 넣어준다.
  5. 2번 ~ 4번 과정을 Queue가 빌 때까지 반복한다.

여기서 최소방문 횟수 및 방문 여부를 확인하기 위해 기록이 필요한 배열(visitedMap)을 따로 만든다. 값이 -1이면 방문 안한 것이고, 0은 시작점, 그외 자연수는 최소 방문 횟수를 의미한다.

이에 대한 로직을 구현한 결과 다음 코드와 같다.

// 정답 용 메서드
private static void findAnswer(char[][] map, int h, int w, int n, int startX, int startY){
    // Queue를 이용한 BFS 최단 거리 찾기
    Queue<Position> queue = new LinkedList<>();
    queue.add(new Position(startX, startY));
    resetVisitedMap(h, w);
    visitedMap[startX][startY] = 0;

    int ans = 0;

    // 1부터 N까지 치즈 먹는 최단 기간 순서대로 구하기
    for(int mouseHealth = 1; mouseHealth <= n; mouseHealth++){

        while (!queue.isEmpty()){
            Position current = queue.poll();
            int currentX = current.getX();
            int currentY = current.getY();

            // 목표지점 도달시 최소거리 누적 및 방문 기록과 출발점 재설정
            if(map[currentX][currentY] == '0' + mouseHealth){
                ans += visitedMap[currentX][currentY];
                queue.clear();
                queue.add(new Position(currentX, currentY));
                resetVisitedMap(h, w);
                visitedMap[currentX][currentY] = 0;
                break;
            }

            // 동서남북 4방향 탐색
            for(int next = 0; next < 4; next++){
                int nextX = currentX + dx[next];
                int nextY = currentY + dy[next];

                // 다음 위치가 범위 내 && 장애물이 아닌 지 && 처음으로 들렸는지?
                if(isRange(nextX, nextY, h, w) && map[nextX][nextY] != 'X' && visitedMap[nextX][nextY] == -1){
                    visitedMap[nextX][nextY] = visitedMap[currentX][currentY] + 1;
                    queue.add(new Position(nextX, nextY));
                }
            }
        }
    }

    //정답 출력
    System.out.println(ans);
}

결론

핵심은 기본적으로 너비 우선 탐색 (BFS)을 아느냐 그리고 어떻게 해결하는지 아느냐이다. 거기에 더한 약간의 향신료는 시작점과 도착점이 달라져서 여러 번 찾게 만드는 것이다.