문제 링크

성능 요약

메모리: 16412 KB, 시간: 132 ms

분류

데이크스트라, 그래프 이론, 최단 경로

제출 일자

2025년 2월 24일 16:23:20

문제 설명

일요일 아침에 형택이는 Maroon5의 Sunday Morning이란 노래를 들으면서 여자친구와의 로맨틱한 여행을 떠나기로 했다. 형택이는 이것저것 환상에 빠져있다가, 계획을 세우는데 실패했다. 따라서, 주위에 있는 숲을 같이 탐험하기로 했다.

깊은 숲속에는 정말 아름다운 꽃이 하나있다. 형택이는 여자친구의 마음을 감동시키기 위해서, 꽃을 보여주면서 자신의 마음을 전해주려고 급하게 계획했다.

불행하게도, 사람들이 숲에다 쓰레기를 버려서 형택이의 계획은 정말 망가지기 직전이다.

형택이는 그동안 여자친구와 사귀면서 2가지 깨달은 것이 있는데, 한 가지는 쓰레기를 통과해서 지나가는 것을 정말 싫어하는 것이고, 쓰레기를 따라 옆을 지나가는 것도 정말 불편하게 느낀다는 것이다.

형택이는 방금 쓰레기가 어디에있는지 조사를 마쳤다. 입력으로 숲의 지도가 주어진다. S는 형택이와 여자친구의 데이트 시작장소를 나타내고, F는 꽃이 있는 위치를 나타내고, g는 쓰레기가 있는 위치를 나타낸다. 그리고 .은 아무것도 없는 깨끗한 칸이다.

형택이의 목표는 S에서 F까지 가는데, 쓰레기로 차있는 칸을 되도록이면 적게 지나가는 것이다. 형택이와 여자친구는 한 번에 한 칸 움직일 수 있다. 가로 or 세로로 한 칸 움직일 수 있다. 만약 되도록 적게 지나가는 경우의 수가 여러개라면, 쓰레기 옆을 지나가는 칸의 개수를 최소로 해서 지나려고 한다. 만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다. 그리고, S와 F는 세지 않는다.

입력

첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있다. S는 반드시 모서리에 위치해 있고, F는 모서리에 위치해있지 않다. 그리고 S와 F는 반드시 하나만 주어진다.

출력

첫째 줄에 형택이와 여자친구가 가장 최적의 방법으로 숲을 지났을 때, 지나가는 쓰레기의 최소 개수를 출력하고, 공백으로 구분 한 후에 쓰레기 옆을 지나가는 칸의 개수를 출력한다.

풀이

느낀점

• 새벽에 집중이 안되는 상태로 대충 풀려고 하다가 해결 못하고 다음날 풀었다.
• 다익스트라 정렬조건만 잘 정리하면 괜찮은 문제였는데, 다익스트라를 제대로 구현 안해놓고 메모리 초과인줄 알고 어떻게 줄일지만 찾았다.. 사실 무한 루프였다.

설계 : 30분

• Node 클래스를 정의해서 해당 칸까지의 이동 경로에 쓰레기를 지나친 횟수와, 쓰레기 옆을 지나간 횟수를 저장하도록 했다.
• dp테이블에는 출발점부터 숲의 각 칸까지의 이동 경로에서 쓰레기를 지나친 최소 횟수, 쓰레기 옆을 지나간 최소 횟수를 저장하도록 했다. (dp 테이블 갱신을 안하고 계속 큐에 넣기만 해서 무한루프가 생겼었다..)
• 쓰레기를 지나친 횟수가 더 적은 순서대로, 이 횟수가 같다면 쓰레기 옆을 지나간 횟수가 더 적은 순서대로 우선순위 큐를 정렬했다.
• poll()한 칸에서 사방탐색을 했을 때, 각각 Node 상태를 생성한 후 dp테이블과의 비교를 통해 더 최적의 경우라면 큐에 추가한다. (큐에 추가할 칸이라면 dp테이블도 해당 값으로 갱신해주어야 한다.)

코드(Java)

• 구현 시간: 160분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 일요일 아침의 데이트_1445
 * Date: 2025.02.24
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        char[][] forest = new char[n][m];

        int[][][] dp = new int[n][m][];
        int[] start = new int[2];
        for (int i = 0; i < n; i++) {
            char[] tmp = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                forest[i][j] = tmp[j];
                if (forest[i][j] == 'S') start = new int[] {i, j};
                dp[i][j] = new int[] {2500, 2500};
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (forest[i][j] != 'g') continue;
                for (int d = 0; d < 4; d++) {
                    int nr = i + dr[d];
                    int nc = j + dc[d];

                    if (nr < 0 || nr >= n || nc < 0 || nc >= m || forest[nr][nc] != '.') continue;
                    forest[nr][nc] = 's';
                }
            }
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(start[0], start[1], 0, 0 ));

        out : while(!pq.isEmpty()) {

            Node curr = pq.poll();

            for (int d = 0; d < 4; d++) {
                int nr = curr.r + dr[d];
                int nc = curr.c + dc[d];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;

                Node next = new Node(nr, nc, curr.gCnt, curr.sCnt);

                if (forest[nr][nc] == 'g') next.gCnt++;
                else if (forest[nr][nc] == 's') next.sCnt++;
                else if (forest[nr][nc] == 'F') {
                    bw.write(String.valueOf(next.gCnt) + " " + String.valueOf(next.sCnt));
                    break out;
                }

                if (dp[nr][nc][0] < next.gCnt
                        || (dp[nr][nc][0] == next.gCnt && dp[nr][nc][1] <= next.sCnt)) continue;

                dp[nr][nc][0] = next.gCnt;
                dp[nr][nc][1] = next.sCnt;
                pq.add(next);
            }
        }

		bw.flush();
		bw.close();
		br.close();
	}
}

class Node implements Comparable<Node> {
    int r;
    int c;
    int gCnt;
    int sCnt;

    Node (int r, int c) {
        this.r = r;
        this.c = c;
        this.gCnt = 2500;
        this.sCnt = 2500;
    }

    Node(int r, int c, int gCnt, int sCnt) {
        this.r = r;
        this.c = c;
        this.gCnt = gCnt;
        this.sCnt = sCnt;
    }

    @Override
    public int compareTo(Node o) {
        if (this.gCnt == o.gCnt) return this.sCnt - o.sCnt;
        return this.gCnt - o.gCnt;
    }
}