[프로그래머스] 미로 탈출 - JAVA

문제

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

프로그래머스

 

 

코드

import java.util.*;

class Solution {
    public int solution(String[] maps) {
        int n = maps.length;
        int m = maps[0].length();
        
        char [][] board = new char [n][m];
        
        int start [] = new int [2];
        int leber [] = new int [2];
        int exit [] = new int [2];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                board[i][j] = maps[i].charAt(j);
                if(board[i][j] == 'S'){
                    start[0] = i;
                    start[1] = j;
                }
                else if(board[i][j] == 'L'){
                    leber[0] = i;
                    leber[1] = j;
                }
                else if(board[i][j] == 'E'){
                    exit[0] = i;
                    exit[1] = j;
                }
            }
        }
        
        int leberDist = leberBfs(n, m, start, board);
        if(leberDist == -1) return -1;
        
        int exitDist = exitBfs(n, m, leber, board);
        if(exitDist == -1) return -1;
        return leberDist+exitDist;
    }
    
    public int leberBfs(int n, int m, int [] start, char [][] board){
        int [] dx = {1, 0, -1, 0};
        int [] dy = {0, 1, 0, -1};
        
        int visited[][] = new int [n][m];
        for(int i=0;i<n;i++) {
            Arrays.fill(visited[i], -1);
        }
        Queue<int []> que = new LinkedList<>();
        
        que.add(new int []{start[0],start[1]});
        visited[start[0]][start[1]] = 0;
        
        while(!que.isEmpty()){
            int cur [] = que.poll();
            
            if(board[cur[0]][cur[1]] == 'L'){
                return visited[cur[0]][cur[1]];
            }
            
            for(int i=0;i<4;i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if(board[nx][ny] == 'X') continue;
                if(visited[nx][ny] == -1 || visited[nx][ny] > visited[cur[0]][cur[1]]+1){
                    que.add(new int [] {nx, ny});
                    visited[nx][ny] = visited[cur[0]][cur[1]]+1;
                }
            }
        }
        return -1;
    }
    
    public int exitBfs(int n, int m, int [] leber, char [][] board){
        int [] dx = {1, 0, -1, 0};
        int [] dy = {0, 1, 0, -1};
        
        int visited[][] = new int [n][m];
        for(int i=0;i<n;i++) {
            Arrays.fill(visited[i], -1);
        }
        Queue<int []> que = new LinkedList<>();
        
        que.add(new int []{leber[0],leber[1]});
        visited[leber[0]][leber[1]] = 0;
        
        while(!que.isEmpty()){
            int cur [] = que.poll();
            
            if(board[cur[0]][cur[1]] == 'E'){
                return visited[cur[0]][cur[1]];
            }
            
            for(int i=0;i<4;i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if(board[nx][ny] == 'X') continue;
                if(visited[nx][ny] == -1 || visited[nx][ny] > visited[cur[0]][cur[1]]+1){
                    que.add(new int [] {nx, ny});
                    visited[nx][ny] = visited[cur[0]][cur[1]]+1;
                }
            }
        }
        return -1;
    }
}

중복되는 코드가 많아 하나의 함수로 합쳤다.

 

최종코드는 다음과 같다.

import java.util.*;

class Solution {
    public int solution(String[] maps) {
        int n = maps.length;
        int m = maps[0].length();
        
        char [][] board = new char [n][m];
        
        int start [] = new int [2];
        int leber [] = new int [2];
        int exit [] = new int [2];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                board[i][j] = maps[i].charAt(j);
                if(board[i][j] == 'S'){
                    start[0] = i;
                    start[1] = j;
                }
                else if(board[i][j] == 'L'){
                    leber[0] = i;
                    leber[1] = j;
                }
                else if(board[i][j] == 'E'){
                    exit[0] = i;
                    exit[1] = j;
                }
            }
        }
        
        int leberDist = bfs(n, m, start, leber, board);
        if(leberDist == -1) return -1;
        
        int exitDist = bfs(n, m, leber, exit, board);
        if(exitDist == -1) return -1;
        return leberDist+exitDist;
    }
    
    public int bfs(int n, int m, int [] start, int [] end, char [][] board){
        int [] dx = {1, 0, -1, 0};
        int [] dy = {0, 1, 0, -1};
        
        int visited[][] = new int [n][m];
        for(int i=0;i<n;i++) {
            Arrays.fill(visited[i], -1);
        }
        Queue<int []> que = new LinkedList<>();
        
        que.add(new int []{start[0],start[1]});
        visited[start[0]][start[1]] = 0;
        
        while(!que.isEmpty()){
            int cur [] = que.poll();
            
            if(cur[0] == end[0] && cur[1] == end[1]){
                return visited[cur[0]][cur[1]];
            }
            
            for(int i=0;i<4;i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if(board[nx][ny] == 'X') continue;
                if(visited[nx][ny] == -1 || visited[nx][ny] > visited[cur[0]][cur[1]]+1){
                    que.add(new int [] {nx, ny});
                    visited[nx][ny] = visited[cur[0]][cur[1]]+1;
                }
            }
        }
        return -1;
    }
}