[SW Expert Academy] 1861 정사각형 방 [Java]

[ 핵심풀이 ]

Dfs로 구현한다면 별 특이사항없이 풀어낼 수 있다.

본인은 Bfs로 진행하며 시간초과를 맛봣기때문에 풀이를 좀 쓰고자한다.

 

문제에선 다음방으로 전진하기위해 수가 1더 커야한다.

1000 x 1000 에 상하좌우로 모든지점에대해서 검색하기때문에

각 좌표에서 모든지점까지 탐색하거나, 작은 숫자의 좌표부터 모든지점을 탐색한다면 시간초과가 발생한다.

또한 두 방법에서 이미 도착한지점에 앞으로 몇번 더 갈 수 있는지 판별해놓아도 마찬가지였다.

 

시간초과를 없애기위해 위 기본풀이를 역으로 생각하여

가장 큰 수의 좌표부터 1씩 감소시키며 탐색하고,

방문된곳은 제거하여 탐색의 시작을 하지않는 방식으로 풀어나갔다.

 

*또다른풀이는 y x a b 4개의 값을통해

좌표와, 현재까지 최대수, 최소 방숫자를 가져가며 풀어내는 방식이있는데,

아직 이풀이로는 풀이하지못하였다.

주먹구구식 방식이라 생각한다. 구현능력을 기르기위한 가장좋은 방법이 아닐까 싶다.

[ Java ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class pair {
    int idx;
    int cnt;
    pair(int idx, int cnt) {
        this.idx = idx;
        this.cnt = cnt;
    }
    public int getIdx() {
        return idx;
    }
    public void setIdx(int idx) {
        this.idx = idx;
    }
    public int getCnt() {
        return cnt;
    }
    public void setCnt(int cnt) {
        this.cnt = cnt;
    }
}

class xy {
    int y;
    int x;
    xy(int y, int x) {
        this.y = y;
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
}

class cost extends xy {
    int cnt;
    cost(int y, int x, int cnt) {
        super(y, x);
        this.cnt = cnt;
    }
    public int getCnt() {
        return cnt;
    }
    public void setCnt(int cnt) {
        this.cnt = cnt;
    }
}

public class _1861_정사각형방 {
    static final int MAX = 1001;
    static int H;

    static int ay[] = { -1, 1, 0, 0 };
    static int ax[] = { 0, 0, -1, 1 };

    static int map[][] = new int[MAX][MAX];
    static boolean visit[][] = new boolean[MAX][MAX];
    static xy index[];
    static pair result;

    static void init() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();

        for (int t = 1; t <= tc; t++) {
            H = sc.nextInt();
            index = new xy[H * H + 1];

            for (int i = 0; i < H; i++)
                for (int j = 0; j < H; j++) {
                    map[i][j] = sc.nextInt();
                    index[map[i][j]] = new xy(i, j);
                }

            for (boolean item[] : visit)
                Arrays.fill(item, false);
			
            result = new pair(H * H + 1, 0);

            for (int i = H * H; i > 0; i--) {
                int y = index[i].getY();
                int x = index[i].getX();
                if (!visit[y][x])
                    solve(y, x);
            }
            System.out.println("#"+t+" "+result.getIdx()+" "+result.getCnt());
        }
    }

    static void solve(int st_y, int st_x) {
        Queue<cost> q = new LinkedList<cost>();
        q.add(new cost(st_y, st_x, 1));
        visit[st_y][st_x] = true;

        while (!q.isEmpty()) {
            cost out = q.poll();
            int y = out.getY();
            int x = out.getX();
            int cnt = out.getCnt();

            //int flag = 0;
            for (int i = 0; i < 4; i++) {
                int ny = y + ay[i];
                int nx = x + ax[i];
                if (!range(ny, nx) && map[y][x] - map[ny][nx] == 1) {
                    visit[y][x] = true;
                    q.add(new cost(ny, nx, cnt + 1));
                    break;
                }
                //flag++;
            }
            //if (flag == 4) {
            if (q.isEmpty()) {
                if (result.getCnt() < cnt) {
                    result = new pair(map[y][x], cnt);
                } else if (result.getCnt() == cnt) {
                    if (result.getIdx() > map[y][x])
                        result.setIdx(map[y][x]);
                }
            }
        }
    }

    static boolean range(int y, int x) {
        return y < 0 || x < 0 || y > H - 1 || x > H - 1 || visit[y][x];
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        init();
    }
}