백준 1445번 <일요일 아침의 데이트>

백준 알고리즘 1445번

https://www.acmicpc.net/problem/1445

1445번: 일요일 아침의 데이트

---

1445번

형택이는 여자친구와 일요일 아침에 데이트를 하기로 했다.

데이트 장소는 숲인데 깊은 숲 속에 꽃이 하나 있다. 형택이는 여자친구에게 그 꽃을 보여주고 싶은데 고려해야 할 점이 있다.

형택이의 여자친구는 쓰레기를 정말 싫어한다. 그래서 형택이는 꽃이 있는 곳까지 쓰레기가 있는 칸을 가장 적게 통과하고, 만약 같은 칸 수를 지난다면 쓰레기 옆을 가장 적게 통과하고 싶다.

형택이를 도와 여자친구가 가장 적게 화낼 때의 통과하는 쓰레기 칸 수와 쓰레기를 지나가는 칸 수를 구하여라.

 

입력으로 첫 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. 그 다음 N개의 줄에 걸쳐 숲의 지도가 주어진다.

숲의 지도는 시작 위치인 S, 도착 위치인 F, 쓰레기가 있는 칸인 g, 그리고 빈 칸인 .으로만 이루어져 있다.

S는 반드시 모서리에 위치해 있으며, S와 F는 반드시 하나만 주어진다. 또한 S와 F는 세지 않는다.

 

출력으로 가장 최적의 방법으로 숲을 지났을 때 통과하는 쓰레기의 최소 개수와 쓰레기 옆을 지나가는 칸의 수를 출력하면 된다.

 

---

문제 해결

처음에는 DFS를 사용해서 풀었다. 

근데 풀다보니 BFS를 사용해서 풀어도 될 거 같아서 내가 좋아하는 BFS로 풀이를 바꿨다!

 

사실 DFS로 제출했을 때, 3%에서 틀렸는데 DFS 문제는 아니었지만 BFS 로 바꿨다.

 

틀렸던 이유는 쓰레기 칸의 옆에 쓰레기가 있을 때, 통과한 쓰레기 칸 수와 지나간 쓰레기 옆 칸 수 둘 다 증가하기 때문이었다.

 

그 부분을 고치니 맞았다!

 

먼저 좌표를 나타내기 위해 Point 클래스를 작성하였고, 큐에 넣는 요소를 나타내는 QElement 클래스를 작성하였다.

Point 클래스는 (x, y) 좌표를 나타내며, QElement 클래스는 좌표와 해당 좌표로 오는데 통과한 쓰레기 칸 수 direct, 지나온 쓰레기 옆 칸 수 side를 가지고 있다.

 

여기서 중요한 부분은 방문체크를 하는 부분이라고 생각한다.

visit 배열은 Point 클래스의 값으로 이루어져있는데 이때 현재 좌표에 최적의 경우로 온 경우의 통과한 쓰레기 칸 수 x와 지나온 쓰레기 옆 칸 수 y를 가지고 있다.

각 좌표에 대한 방문은 아래와 같은 경우에 할 수 있다.

• visit 배열의 값이 null인 경우 -> 처음 온 경우이기 때문에 방문 가능
• visit 배열의 값에서 x 값이 만약 현재 경우의 통과한 쓰레기 칸 수보다 크다면
  • -> 더 적은 쓰레기를 통과해서 올 수 있기 때문에 방문 가능
• visit 배열의 값에서 x값이 현재 경우의 통과한 쓰레기 칸 수와 같고 y값이 현재 경우의 지나온 쓰레기 옆 칸 수보다 크다면
  • -> 더 적은 쓰레기를 지나서 올 수 있기 때문에 방문 가능

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class BOJ_1445 {
    static int N, M;        // N : 세로길이     M : 가로 길이
    static int ansDirect, ansSide;
    static Point S;      // S : 시작 위치
    static int[] di = {1, -1, 0, 0};
    static int[] dj = {0, 0, 1, -1};
    static char[][] MAP;
    // visit[i][j] : (i, j) 좌표에서 x : 쓰레기를 통과하는 칸 최소 값, y : 쓰레기 옆을 지나는 칸 최소값
    static Point[][] visit;
    static class Point{
        int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static class QElement{
        Point pnt;
        int direct, side;

        public QElement(Point pnt, int direct, int side) {
            this.pnt = pnt;
            this.direct = direct;
            this.side = side;
        }

        public QElement(Point pnt) {
            this.pnt = pnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        M = Integer.parseInt(inArr[1]);
        MAP = new char[N][];
        for (int i = 0; i < N; i++) {
            MAP[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if (MAP[i][j] == 'S'){
                    S = new Point(i, j);
                }
            }
        } // end input

        visit = new Point[N][M];
        ansDirect = Integer.MAX_VALUE;
        ansSide = Integer.MAX_VALUE;
        BFS(S);
        System.out.printf("%d %d", ansDirect, ansSide);

    }
    static void BFS(Point start){
        Queue<QElement> Q = new ArrayDeque<>();
        visit[start.x][start.y] = new Point(0, 0);
        Q.add(new QElement(start, 0, 0));
        while (!Q.isEmpty()) {
            QElement element = Q.poll();

            for (int k = 0; k < 4; k++) {
                int nx = element.pnt.x + di[k];
                int ny = element.pnt.y + dj[k];
                // 범위 벗어나면 안됨
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (MAP[nx][ny] == 'F') { // 도착지 도착
                    if (ansDirect > element.direct) {       // 정답(통과하는 칸 수)가 더 크면 바꾸기
                        ansDirect = element.direct;
                        ansSide = element.side;
                    } else if (ansDirect == element.direct && ansSide > element.side) {
                        // 정답(통과하는 칸 수는 같고 지나는 칸 수)가 더 크면 바꾸기
                        ansSide = element.side;
                    }
                    continue;
                }

                Point pnt = new Point(nx, ny);
                QElement temp = new QElement(pnt, element.direct, element.side);
                if (MAP[nx][ny] == 'g') temp.direct++;  // g면 통과하는 거
                else if (isSide(pnt)) temp.side++;           // 옆이면 지나가는 거
                // visit 배열 값이 null이거나
                // visit 배열 값의 x값이 temp.direct보다 크거나
                // visit 배열 값의 x값이 temp.direct과 같고 y값이 temp.side보다 크다면
                // -> 방문 가능
                if (visit[nx][ny] == null || visit[nx][ny].x > temp.direct ||
                        (visit[nx][ny].x == temp.direct && visit[nx][ny].y > temp.side)) {
                    visit[nx][ny] = new Point(temp.direct, temp.side);
                    Q.add(temp);
                }
            }
        }
    }

    static boolean isSide(Point pnt) {
        for (int k = 0; k < 4; k++) {
            int nx = di[k] + pnt.x;
            int ny = dj[k] + pnt.y;
            if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                continue;
            if (MAP[nx][ny] == 'g'){
                return true;
            }
        }
        return false;
    }
}

---

결과

 

---

3 3
.S.
ggg
..F

1 1
----------
3 4
.S..
g..g
.g.F

0 2
----------
2 2
.S
.F

0 0
----------
2 2
Fg
gS

1 0
----------
3 3
ggg
gFg
ggS

1 0
----------