Q. 1226. 미로 1(D4)

Q. 1226. 미로 1(D4)

 

0. 문제

 

D4 난이도의 문제이지만, 그정도는 아닌 것 같고

단순 그래프 탐색 문제이다.

이동할 수 있는 칸, 이동할 수 없는 칸, 시작 위치, 종료 위치가 주어졌을 때

이동할 수 있는지 계산하는 문제이다.

---

1. 풀이

 

전형적인 그래프 탐색 문제이다.

BFS를 이용해 풀이했고, 아래와 같은 방식으로 풀었다.자료형은 갈수 없는 벽과 갈 수 있는벽으로 나눠지므로 boolean 타입을 사용했다.

 

1. 입력을 받으면서 갈 수 있는 벽인지 여부를 저장한다. 또한 시작 위치와 종료 위치도 저장한다.2. 종료 위치에서부터 BFS 탐색을 시작하며, 이전에 방문했던 곳은 표시를 해서 재방문하지 않도록 한다.3. 만약 시작 위치에 도달했을 경우 즉시 루프를 종료하고, 결과를 저장한다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Solution {
 
    static BufferedReader br;
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;
     
 
    static int N = 16;
    static boolean[][] board;
    static boolean[][] visit;
    static int[] startIdx;
    static int[] endIdx;
     
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
     
    static void input() throws IOException {
         
        board = new boolean[N][N];
        visit = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            char[] inputChar = br.readLine().toCharArray();
            for(int j = 0; j < N; j++) {
                if (inputChar[j] == '0') {
                    board[i][j] = true;
                    continue;
                }
                if(inputChar[j] == '1') {
                    visit[i][j] = true;
                    continue;
                }
                if(inputChar[j] == '2') { // start
                    board[i][j] = true;
                    startIdx = new int[] {i, j};
                    continue;
                }
                if(inputChar[j] == '3') { // end
                    endIdx = new int[] {i, j, 0};
                    board[i][j] = true;
                }
                 
            }
        }
    }
     
    static void pro(int tc) throws Exception{
         
        boolean res = false;
        Deque<int[]> que = new LinkedList<>();
        que.add(endIdx);
        visit[endIdx[0]][endIdx[1]] = true;
         
        while(!que.isEmpty()) { // bfs
             
            int[] curIdx = que.poll(); // int[3] = y, x, move
            if (curIdx[0] == startIdx[0] && curIdx[1] == startIdx[1]) {
                res = true;
                break;
            }
             
            for (int i = 0; i < 4; i++) {
                int ny = curIdx[0] + dy[i];
                int nx = curIdx[1] + dx[i];
                 
                if (ny == -1 || nx == -1 || ny == N || nx == N) continue;
                if (visit[ny][nx]) continue;
                 
                visit[ny][nx] = true;
                que.add(new int[] {ny, nx, curIdx[2] + 1});
                 
            }
        }
        sb.append(String.format("#%d %d\n", tc, res? 1 : 0));
    }
     
    public static void main(String[] args) throws Exception{
         
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
         
        int T = 10;
        for(int tc = 1; tc <= T; tc++) {
            int i = Integer.parseInt(br.readLine());
            input();
            pro(i);
        }
        System.out.println(sb);
         
    }
 
}

---

2. 시간복잡도 계산

 

0) N의 최대값은 16이다.

1) 입력값 저장 - O(N^2)

2) 풀이 2, 3번(최악의 경우 모든 정점을 탐색)  - O(N^2)

두 연산는 연관이 없으므로 덧셈으로 계산하면 된다. 따라서 시간복잡도는 O(N^2)이고,

시간제한은 2초이므로 1초에 약 1억번 연산을 한다고 가정하면, 1초 이내에 풀 수 있다.

---

3. 성능 개선 방향

 

케이스마다 다르겠지만, 탐색을 시작 위치를 도착 위치부터 출발 위치부터 찾는 방식으로 했다.

이 경우 도착 위치 근처가 막혀 있는 경우 성능 개선의 여지가 있다.

(출발 위치 근처가 막혀 있는 경우는 더 느리다.)

또한 미로를 저장하는 배열의 타입을 bool 형으로 저장해서, 공간 복잡도를 줄였다.