자바(백준) 17836 공주님을 구해라!

오답 노트 & 새로 알게 된 점

문제를 읽으면 그램을 가졌을 때는 벽을 통과할 수 있다.

 

그렇다면 문제 접근할 때는 그램 없이 목적지에 도착하는 시간과 그램을 가지고 목적지에 도착하는 시간 중

더 작은 값을 구하면 된다.

 

여기서 중요한 점은 visit를 3차원 배열로 만들었는지가 아닌가 싶다.

왜냐하면 

2차원 배열로 만들었을 경우, 그림과 같이 빨간색 동그라미 부분을 그램을 가지지 않고 먼저 방문했을경우,

그램을 가지고 저 부분을 지나칠 수 없게 된다. 

 

그래서 그램을 가진 상태로 방문을 했는지, 가지지 않은 상태에서 방문을 했는지 나타내기 위해 visit를 3차원 배열로 만들어야한다.

 

---

코드1

package bfs_dfs;
 
import java.io.*;
import java.util.*;
 
public class BOJ17836 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M, T;
    static int A[][];
    static boolean visit[][][]; //0이면 그람없이 1이면 그람있이
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        bfs();
 
        if(ans == Integer.MAX_VALUE) System.out.println("Fail");
        else System.out.println(ans);
    }
 
    static void bfs() {
        Queue<Point> q = new ArrayDeque<>();
        q.offer(new Point(0, 0, 0, 0));
        visit[0][0][0] = true;
 
        while (!q.isEmpty()) {
            Point p = q.poll();
 
            if(p.x == N - 1 && p.y == M - 1){
                if(p.cnt <= T) ans = Math.min(ans, p.cnt);
                return;
            }
 
            if(A[p.x][p.y] == 2) p.gram = 1;
 
            for (int i = 0; i < 4; i++) {
                int X = p.x + dx[i];
                int Y = p.y + dy[i];
 
                if(!isRangeTrue(X,Y)) continue;
 
                if(p.gram == 0){
                    if(visit[X][Y][0]) continue;
                    if(A[X][Y] == 1) continue;
 
                    q.offer(new Point(X, Y, p.cnt + 1, p.gram));
                    visit[X][Y][0] = true;
                }
                else{
                    if(visit[X][Y][1]) continue;
 
                    q.offer(new Point(X, Y, p.cnt + 1, p.gram));
                    visit[X][Y][1] = true;
                }
            }
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
        T = atoi(st.nextToken());
 
        A = new int[N][M];
        visit = new boolean[N][M][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                A[i][j] = atoi(st.nextToken());
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
 
    static class Point{
        int x, y, cnt, gram;
 
        public Point(int x, int y, int cnt, int gram) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.gram = gram;
        }
    }
}
 
 
 

 

코드2

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
 
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    static int N, M, limit, ans = Integer.MAX_VALUE;
    static int A[][];
    static boolean visit[][][]; //0이면 그람 X, 1이면 그람
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        Queue<Info> q = new ArrayDeque<>();
        q.offer(new Info(0, 0, 0, 0));
        visit[0][0][0] = true;
 
        while (!q.isEmpty()) {
            Info info = q.poll();
 
            if(A[info.x][info.y] == 2) info.gram = 1;
 
            if(info.x == N - 1 && info.y == M - 1){
                ans = Math.min(info.time, ans);
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                int X = info.x + dx[i];
                int Y = info.y + dy[i];
 
                if(!isRangeTrue(X,Y)) continue;
                if(visit[X][Y][info.gram]) continue;
 
                if(info.gram == 0) {
                    if (A[X][Y] == 1) continue;
                }
                q.offer(new Info(X, Y, info.gram, info.time + 1));
                visit[X][Y][info.gram] = true;
            }
        }
 
        if(ans == Integer.MAX_VALUE || ans > limit) System.out.println("Fail");
        else System.out.println(ans);
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        M = atoi(st.nextToken());
        limit = atoi(st.nextToken());
 
        visit = new boolean[N][M][2];
        A = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                A[i][j] = atoi(st.nextToken());
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
 
    static class Info{
        int x, y, gram, time;
 
        public Info(int x, int y, int gram, int time) {
            this.x = x;
            this.y = y;
            this.gram = gram;
            this.time = time;
        }
    }
}