2022.06.30 백준 Q2178

 

 

 

학습 내용 : DFS, BFS의 차이점(어떤 것으로 구현해야 할지), 미로문제 구현방법

 

https://www.acmicpc.net/problem/2178

 

이 문제는 미로 문제를 구현하는 방법에 대해 묻는 문제이다. 미로 문제를 통해 (N,M)로 가는 가장 짧은 경로를 출력해야한다. 필자는 노드를 Class로 구현해 n,m,1인지0인지 유무(isOpened), 방문했던 노드인지(isVisited) 그 곳까지 가는 가장 짧은 경로(length)를 담았다. 그리고 가장 가에 있는 노드들을 다른 노드들과 똑같이 움직일수 있게 통일성을 맞추기 위해 겉을 0으로 감쌌다

ex)

10

01

->

0000

0100

0010

0000

 

또한 이 문제는 최단 경로를 찾아야하기 때문에 DFS가 아닌 BFS로 구현해야한다. BFS를 통해 거리가 2인 노드를 큐에 넣고 다 완료됐으면 거리가 3인 노드를 넣고... 마지막으로 [N,M]에 도착하면 그 legth를 출력하게 하면 된다.

 

 

static int[] dUD = {0, 0, 1, -1};
static int [] dRL = {1,-1,0,0};

윗 코드는 오른쪽,왼쪽,위,아래일때 index의 변화를 나타내는 배열들이다

둘의 index를 같게 하면 칸을 움직일 수 있다.

while(true){
    Node currentNode = q.poll();
    currentN=currentNode.getN(); currentM=currentNode.getM();
    for(int i=0;i<4;i++){
        int newN = currentN+dUD[i]; int newM = currentM+dRL[i];
        if((!maze[newN][newM].getIsVisited())&& (maze[currentN+dUD[i]][currentM+dRL[i]].getIsOpen())){
            q.add(maze[newN][newM]);
            maze[newN][newM].setVisited();
            maze[newN][newM].setLength(currentNode.getLength()+1);
            if(newN==n&&newM==m){
                System.out.println(maze[newN][newM].getLength());
                return;
            }
        }
    }
}

처음 (1,1)의 legth를 1로 설정하고 큐에서 한 값을 꺼내온다(가장 작은 거리를 가지고 있을 것이다) 그 노드의 N,M을 get으로 가지고 오고 각 방향으로 나아가 1(isOpened)인지 방문한적이 있는지 확인한다

만약 방문한 적이 있다면 queue에 넣고 방문 한 걸로 셋팅한다. 그리고 그 길이는 현재있는 노드의 길이에서 1더한 값이므로 currentNode.getLength()+1로 다시 설정한다.

 

 

-구현 코드-

package BaekJoon2178;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


class Node{
    private int n;
    private int m;
    private boolean isOpen;
    private boolean isVisited;
    private int length;
    Node(int n,int m,int i){
        this.n=n;
        this.m=m;
        isOpen=true;
    }
    Node(int n,int m){
        this.n=n;
        this.m=m;
    }
    int getLength(){return length;}
    boolean getIsVisited(){return isVisited;}
    boolean getIsOpen(){return isOpen;}
    void setVisited(){isVisited=true;}
    void setLength(int i){length=i;}
    int getN(){
        return n;
    }
    int getM(){
        return m;
    }
}

public class Main {
    static int[] dUD = {0, 0, 1, -1};
    static int [] dRL = {1,-1,0,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Node [][] maze = new Node[n+2][m+2];
        for(int i=0;i<m+2;i++){
            maze[0][i]=new Node(0,i);
            maze[n + 1][i] = new Node(n + 1, i);
        }
        for(int i=1;i<n+1;i++){
            maze[i][0] = new Node(i, 0);
            maze[i][m + 1] = new Node(i, m + 1);
        }
        for(int i=1;i<=n;i++){
            String str = br.readLine();
            for(int j=0;j<m;j++){
                if(str.charAt(j)=='1') maze[i][j+1]=new Node(i,j+1,1);
                else maze[i][j+1]= new Node(i,j+1);
            }
        }
        Queue<Node> q = new LinkedList<>();
        int currentN=1; int currentM=1;
        q.add(maze[1][1]);
        maze[1][1].setVisited();
        maze[1][1].setLength(1);
        while(true){
            Node currentNode = q.poll();
            currentN=currentNode.getN(); currentM=currentNode.getM();
            for(int i=0;i<4;i++){
                int newN = currentN+dUD[i]; int newM = currentM+dRL[i];
                if((!maze[newN][newM].getIsVisited())&& (maze[currentN+dUD[i]][currentM+dRL[i]].getIsOpen())){
                    q.add(maze[newN][newM]);
                    maze[newN][newM].setVisited();
                    maze[newN][newM].setLength(currentNode.getLength()+1);
                    if(newN==n&&newM==m){
                        System.out.println(maze[newN][newM].getLength());
                        return;
                    }
                }
            }
        }

    }
}