[BOJ - Gold IV] 녹색 옷 입은 애가 젤다지? / ⭕

녹색 옷 입은 애가 젤다지?

1. 제출 코드 (39분 29초 / BFS)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_4485 {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int index = 1;
        N = Integer.parseInt(br.readLine());
        int[][] map;
        while(N != 0) {
            map = new int[N][N];

            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            System.out.println("Problem " + index + ": " + bfs(map));
            N = Integer.parseInt(br.readLine());
            index++;
        }
    }

    public static int bfs(int[][] map) {
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> {
            return Integer.compare(o1[2], o2[2]);
        });
        q.add(new int[] {0, 0, map[0][0]});
        int[][] visited = new int[N][N];
        for(int i = 0; i < N; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        visited[0][0] = map[0][0];

        int answer = Integer.MAX_VALUE;
        while(!q.isEmpty()) {
            int[] t = q.poll();

            if(t[0] == N - 1 && t[1] == N - 1) {
                answer = Math.min(answer, t[2]);
                continue;
            }

            for(int i = 0; i < 4; i++) {
                int nx = t[0] + dx[i];
                int ny = t[1] + dy[i];

                if(nx >= N || nx < 0 || ny >= N || ny < 0) {
                    continue;
                }
                int temp = t[2] + map[nx][ny];
                if(visited[nx][ny] <= temp) continue;
                visited[nx][ny] = temp;
                q.add(new int[]{nx, ny, temp});
            }
        }
        return answer;
    }
}

 

2. 구현 로직

0, 0에서 N-1, N-1까지 BFS로 탐색을 하면 되는데 처음에는 단순히 ArrayDeque를 이용해서 구현을 했더니 메모리 초과 오류가 발생했다. 그래서 우선순위 큐를 활용하여 최단 거리를 가지는 노드부터 빼내서 방문 배열의 최단 거리를 업데이트해줬다.

1. 우선순위 큐를 만들어 시작 지점인 0,0과 시작 지점의 값 map[0][0] 값을 삽입
2. 방문 배열을 하나 생성하고 모두 Integer.MAX_VALUE로 초기화
3. 하나씩 q에서 빼서 주변을 탐색하는데 방문 배열을 함께 검사하여 가려는 곳이 현재 값보다 작다면 패스
4. 크다면 q에 넣어주고 방문 배열 값을 업데이트

3. 유의할 점

• ArrayDeque를 사용하면 메모리 초과가 나니까 최대한 q에 들어가지 못하게 하기 위해서는 우선 순위 큐를 활용하여 answer의 값을 최소한으로 만드는 게 중요한 거 같다.