[프로그래머스] Lv.2 미로 탈출 JAVA 풀이

문제 Lv.2 미로 탈출

 :  직사각형 격자 형태의 미로
    벽으로 된 칸 이동 불가
    통로로 된 칸 이동 가능

 :  출력 = 입구-레버-출구까지 거치는 최소의 탈출 길이
    (탈출할 수 없다면 -1 출력)

 :  출발 레버 출구 모두 따로따로
    입구 → 레버 열기 위해 방문 → 나가기 위해 출구 방문 순으로 미로를 탈출한다 

:   미로를 나타내는 문자열배열 = maps
    maps 자체는 길이가 5 ~ 100
    maps 배열 중 한 묶음은 5개의 문자로 이루어짐 (S: 시작, E: 출구, L: 레버, O: 통로, X: 벽)

    Ex)   maps = ["SOOOL", "XXXXO", "OOOOO", "OXXXX", "OOOOE"]

            이때 maps의 길이는 5이다

 

 

[설명]

 

 BFS 

 

 

 현재 정점에 연결된 가까운 점들부터 탐색

 

 Queue를 사용해서 구현

 

 

 

 

 [코드]

import java.util.*;

class Solution {
    static char[][] arr;
    static boolean[][] visit;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};


    public int solution(String[] maps) {
        int a = maps.length;
        int b = maps[0].length();

        int[] start = new int[2];
        int[] lever = new int[2];
        int[] end = new int[2];

        arr = new char[a][b];
        visit = new boolean[a][b];

        for(int i = 0; i<a; i++) {
            for(int j =0; j<b; j++){

                arr[i][j] = maps[i].charAt(j);

                if (arr[i][j]=='S') {
                    start = new int[]{i,j};
                }

                if (arr[i][j]=='L') {
                    lever = new int[]{i,j};
                }     

                if (arr[i][j]=='E') {
                    end = new int[]{i,j};
                }     
            }
        }

        int Midpoint = bfs(start,lever);
        visit = new boolean[a][b];
        
        int Endpoint = bfs(lever,end);

        if (Midpoint == 0 || Endpoint == 0){
           return -1;
        }

        return Midpoint + Endpoint;
    }


    public int bfs(int[] node1, int[] node2) {
        Queue<int[]> q = new LinkedList<>();
        
        q.add(new int[]{node1[0], node1[1], 0});

        while(!q.isEmpty()) {
              int[] p = q.poll();
              visit[p[0]][p[1]] = true;

              for(int i = 0; i<4; i++) {
                  int nx = p[0] + dx[i];
                  int ny = p[1] + dy[i];

                   if(nx>=0 && nx<arr.length && ny>=0 && ny<arr[0].length && arr[nx][ny]!='X' && !visit[nx][ny]){
                    visit[nx][ny]=true; 
                    q.add(new int[]{nx, ny, p[2]+1});

                   }
              }

              if(p[0]==node2[0] && p[1]==node2[1]) {
                  return p[2];
              } 
        }
        return 0;
    }
}

 :  static char[][] arr;  arr배열 만들기 (문자로 이루어져 있어서 char형으로 받음)
    static boolean[][] visit;  방문기록 확인
    static int[] dx = {-1, 1, 0, 0};  상하좌우 이동 x 좌표
    static int[] dy = {0, 0, -1, 1};  상하좌우 이동 y 좌표

 

 :  int a = maps.length;  배열 행
    int b = maps[0].length();  배열 열
    int[] start = new int[2]; 시작 좌표 x,y 배열에 넣기
    int[] lever = new int[2];  레버 좌표 x,y 배열에 넣기
    int[] end = new int[2];  출구 좌표 x,y 배열에 넣기

 

 

 :  arr = new char[a][b];  arr 배열 지정

    visit = new boolean[a][b]; 방문기록 배열 지정

 :  for(int i = 0; i<a; i++) {   maps의 묶음 개수 만큼 행 만들기
           for(int j =0; j<b; j++){   maps 중에 maps[0] 기준으로 잡고 그 길이 만큼 열 만들기

                arr[i][j] = maps[i].charAt(j);  maps에 있는 문자들 arr 배열에 모두 복사

                if (arr[i][j]=='S') {  입력 받은 문자에 S가 있다면 시작지점
                    start = new int[]{i,j};  시작지점 좌표 start에 저장
                }
                if (arr[i][j]=='L') {  입력 받은 문자에 L가 있다면 레버지점
                    lever = new int[]{i,j};  레버지점 좌표 lever에 저장
                }     
                if (arr[i][j]=='E') {  입력 받은 문자에 E가 있다면 출구지점
                    end = new int[]{i,j};  출구지점 좌표 end에 저장
                }     
           }

    }

 :  int Midpoint = bfs(start,lever);  start ~ lever 지점까지 bfs 돌리기
    visit = new boolean[a][b];  시작~레버까지 bfs돌리고 레버~끝까지 다시 bfs 돌려야해서 visit 초기화
        
    int Endpoint = bfs(lever,end); lever ~ end 지점까지 bfs 돌리기

 :  if (Midpoint == 0 || Endpoint == 0){  두 지점 중에 하나라도 0값이 출력된다면 길이 없어서 탈출 불가
           return -1;  탈출이 불가할 경우 -1 출력
     }

     return Midpoint + Endpoint;  두 개의 탈출 경로를 합쳐 최종 탈출길이 출력
    

 :  public int bfs(int[] node1, int[] node2) {  bfs를 node1지점에서 시작해 node2지점까지 돌린다
          Queue<int[]> q = new LinkedList<>();  큐 생성
          q.add(new int[]{node1[0], node1[1], 0});  출발할 지점, 목표하는 도착지점, 거리 count 값
                                                                           Midpoint 일 때는 bfs 초기값 (start, lever, 0)
                                                                           Endpoint 일 때는 bfs 초기값 (lever, end, 0)
          while(!q.isEmpty()) {
                int[] p = q.poll();  큐에서 뺀 값들 p배열에 저장 (node1[0] = i = x좌표, node1[1] = j = y좌표) 
                visit[p[0]][p[1]] = true;  p[0]은 출발지점, p[1]은 도착지점, p[2]는 거리 count한 값

                for(int i = 0; i<4; i++) {  상, 하, 좌, 우 4가지 방향 탐색
                      int nx = p[0] + dx[i];  새로운 x좌표 = 현 x 좌표 + 이동가능한 방향의 x 좌표
                      int ny = p[1] + dy[i];  새로운 y좌표 = 현 y 좌표 + 이동가능한 방향의 y 좌표

                      if(nx>=0 && nx<arr.length && ny>=0 && ny<arr[0].length  새좌표가 0 ~ arr 사이에 위치
                      && arr[nx][ny]!='X' && !visit[nx][ny]){  방문기록 없을 경우, 해당 좌표에 "X"란 문자 없다면
                                                                                   (해당 좌표에 "X" 문자 없다면 벽이 아니므로 이동가능)
                           visit[nx][ny]=true;  방문처리
                           q.add(new int[]{nx, ny, p[2]+1});  큐에 새로운 x좌표, y좌표, 거리를 1씩 count 해준다
                      }
                }

                if(p[0]==node2[0] && p[1]==node2[1]) {  현 x좌표 = 목표 x좌표, 현 x좌표 = 목표 y좌표라면
                          return p[2];  그대로 그동안 count한 거리 p[2] 를 출력
                } 
         }
         return 0;  탈출 경로 찾을 수 없다면 0으로 return
   }

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *