[BOJ ]미로 탐색(2178)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

난이도 : 실버1(solved.ac참조)

알고리즘 분류 : BFS, DFS

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static int N, M;
    static int[][] mtx;
    static int[] dy = {1,-1, 0, 0};
    static int[] dx = {0, 0, 1,-1};
    static class Node{	// 현재 위치(x,y)와 몇번째 칸인지 나타내는 변수(count)를 담음
        private int x,y;
        private int count;
        Node(int y, int x, int count){
            this.y=y;
            this.x=x;
            this.count=count;
        }
        public int getX() { return x;}
        public int getY() { return y;}
        public int getCount() { return count;}

        public void setX(int x) { this.x = x;}
        public void setY(int y) { this.y = y;}
        public void setCount(int count) { this.count = count;}

        public boolean check(){			// 갈 수 있는 칸인지 확인
            if(mtx[y][x]==1) return true;
            else return false;
        }
        public void setZero(){			// 방문한 칸을 1->0으로 바꿔줘 무한루프 방지
            mtx[y][x]=0;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        mtx=new int[N+2][M+2];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken().toString();
            for(int s = 0; s<str.length(); s++){
                if(str.charAt(s)=='1') mtx[i][s+1]= 1;
                else mtx[i][s+1]= 0;
            }
        }
        
        Queue<Node> q = new LinkedList<>();

        q.add(new Node(1,1, 1));
        while(!q.isEmpty()){
            Node node = q.poll();
            if(node.getY()==N && node.getX()==M){
                System.out.println(node.getCount());
                break;
            }
            for(int i =0; i< 4; i++){
                Node newN = new Node(node.getY()+dy[i],node.getX()+dx[i], node.getCount()+1);
                if(newN.check()){   // mtx[][]가 1이면
                    newN.setZero();
                    q.add(newN);
                }
            }

        }
    }

}

풀이

단순한 BFS나 DFS로 풀면 되는 문제이다.

하지만 최소 방문 수를 구할 때는 BFS가 더 빠르게 구할 수 있으므로 BFS를 선호한다.

다만 자바를 이용해서 이러한 문제를 푸는 것은 처음이라 Node클래스를 만드는게 실제 코딩테스트에서 효율적인가 의문이 들긴 한다.

 

※다른 사람의 코드를 보니 자바에서 코딩테스트를 할 때는 getter나 setter등 자바 클래스를 사용할 때 필수적인 요소라고 생각했던 것들을 사용하지 않는 것같다. 빠르게 풀어내는게 중요하다보니 대부분 이렇게 사용하는 것이라고 이해가 된다.

 

수정코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static int N, M;
    static int[][] mtx;
    static int[] dy = {1,-1, 0, 0};
    static int[] dx = {0, 0, 1,-1};
    static class Node{
        int x,y;
        int count;
        Node(int y, int x, int count){
            this.y=y;
            this.x=x;
            this.count=count;
        }

        public boolean check(){
            if(mtx[y][x]==1) return true;
            else return false;
        }
        public void setZero(){
            mtx[y][x]=0;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        mtx=new int[N+2][M+2];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken().toString();
            for(int s = 0; s<str.length(); s++){
                mtx[i][s+1] = str.charAt(s)-'0';	// 이부분도 수정했다.
            }
        }
        
        Queue<Node> q = new LinkedList<>();

        q.add(new Node(1,1, 1));
        while(!q.isEmpty()){
            Node node = q.poll();
            if(node.y==N && node.x==M){
                System.out.println(node.count);
                break;
            }
            for(int i =0; i< 4; i++){
                Node newN = new Node(node.y+dy[i],node.x+dx[i], node.count+1);
                if(newN.check()){   // mtx[][]가 1이면
                    newN.setZero();
                    q.add(newN);
                }
            }

        }
    }

}