🎯문제
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.
미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.
제한사항
- 5 ≤ maps의 길이 ≤ 100
- 5 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
- S : 시작 지점
- E : 출구
- L : 레버
- O : 통로
- X : 벽
- 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
- 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.
입출력 예
maps| result
:---:|:---:
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]| 16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]| -1
입출력 예 설명
입출력 예 #1
주어진 문자열은 다음과 같은 미로이며
다음과 같이 이동하면 가장 빠른 시간에 탈출할 수 있습니다.
4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.
입출력 예 #2
주어진 문자열은 다음과 같은 미로입니다.
시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.
✏️풀이
코드
import java.util.*;
class Solution {
// map 저장 배열
char[][] map;
// x, y 좌표로 이동하기 위한 배열
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};
// bfs 탐색 메서드
public int bfs(int x, int y, char t) {
// 큐 생성
Queue<int[]> q = new LinkedList<>();
// 초깃값을 넣어줌
q.add(new int[]{x, y, 0});
// 방문 여부를 저장할 배열
boolean[][] visit = new boolean[map.length][map[0].length];
// 큐에 값이 없을 때까지 반복
while(!q.isEmpty()) {
// 큐에서 값을 하나 가져옴
int[] temp = q.poll();
// 현재 x, y 좌표와 count
int nx = temp[0];
int ny = temp[1];
int count = temp[2];
// 방문여부를 true로 변경
visit[nx][ny] = true;
// 해당 위치가 target과 일치할 경우 현재 count를 반환
if(map[nx][ny] == t) {
return count;
}
// 좌표를 이동
for(int i = 0; i < 4; i++) {
// dx, dy 배열을 사용해서 x, y좌표를 이동
int mx = nx + dx[i];
int my = ny + dy[i];
// 움직인 x, y 좌표가 map의 범위 안에 있으면서
// 방문한 적이 없고 갈 수 없는 곳이 아니라면
if(mx >= 0 && my >= 0 && mx < map.length && my < map[0].length
&& !visit[mx][my] && map[mx][my] != 'X') {
// 해당 방문 여부를 true로 바꿔주고
visit[mx][my] = true;
// 큐에 값을 넣어줌
q.add(new int[]{mx, my, count + 1});
}
}
}
// target에 가지 못하고 반복문을 빠져나왔다면 -1을 반환
return -1;
}
public int solution(String[] maps) {
// map을 생성
map = new char[maps.length][maps[0].length()];
// 시작위치를 저장할 변수들
int sx = 0, sy = 0, lx = 0, ly = 0;
for(int i = 0; i < maps.length; i++) {
for(int j = 0; j < maps[0].length(); j++) {
// map에 값을 넣어줌
map[i][j] = maps[i].charAt(j);
// 현재 위치가 레버일 경우
if(map[i][j] == 'L') {
// lx, ly에 레버의 위치를 저장
lx = i;
ly = j;
}
// 현재 위치가 시작점일 경우
else if(map[i][j] == 'S') {
// sx, sy에 시작점의 위치를 저장
sx = i;
sy = j;
}
}
}
// 시작점부터 레버까지 bfs 탐색을 진행
int result1 = bfs(sx, sy, 'L');
// 레버부터 도착점까지 bfs 탐색을 진행
int result2 = bfs(lx, ly, 'E');
// bfs 탐색 결과 중 하나라도 -1이 나온다면 -1을 아니라면 두 값을 더해서 반환
return (result1 == -1 || result2 == -1) ? -1 : result1 + result2;
}
}설명
bfs 탐색을 사용해서 진행하였다.
map을 저장할 char형 2차원 배열을 만들고 상하좌우로 이동해주기 위한 dx, dy 배열을 생성해준다.
bfs 탐색 메서드에서 x, y와 t가 매개 변수로 주어지는데 x, y는 탐색을 시작할 x, y좌표이며, t는 target으로 해당 값이 나올 때까지 탐색을 하겠다는 뜻이다.
큐를 생성하고 초깃값을 넣어준다. 큐는 int[]형을 넣어주며 int[]에는 x, y좌표와 탐색횟수를 넣어준다. 또한 방문여부를 저장할 배열을 생성한다.
이후 반복문을 진행하는데 반복의 조건은 큐에 값이 없을때까지이다. 큐에 있는 값에서 하나를 가져와서 x, y, count의 값에 각각 넣어준다. 이후 방문여부를 true로 변경한 뒤에 해당 위치가 target과 일치하는지 확인한다. 일치할 경우 현재 count를 반환해주고, 일치하지 않는다면 좌표를 이동시킨다. 이동할 때는 dx, dy 배열을 사용해서 좌표를 이동한다.
이동한 좌표가 map의 범위 안에 있으면서, 방문한 적이 없고, 갈 수 있는 길이라면 해당 위치의 방문 여부를 true로 바꿔주고 큐에 값을 넣어준다.
위의 반복을 진행하면서 target과 일치하는 부분까지 탐색이 진행이 됐다면 count가 반환이 되고, target까지 탐색이 가지 못한다면 반복문을 빠져나와 -1을 반환하게 된다.
solution 메서드에서는 map을 생성하고 반복문을 사용하여 값을 넣어준다. 이때 sx, sy, lx, ly라는 각각의 변수에 시작점의 위치와 레버의 위치를 저장한다. bfs 탐색은 시작점에서 레버까지, 레버에서 도착점까지 2번의 탐색이 필요하기 때문이다. 따라서 시작점의 x, y좌표를 sx, sy에 레버의 x, y좌표를 lx, ly에 저장한다.
이후 시작점부터 레버의 위치까지 bfs 탐색을 진행하여 나온 값을 result1에, 레버의 위치부터 도착점까지 bfs 탐색을 진행하여 나온 값을 result2에 저장한다.
모든 탐색이 끝난 뒤 result1과 result2의 값을 확인하여 하나라도 -1이 있다면 -1을 모두 -1이 아니라면 둘을 더한 값을 반환해주면 문제를 해결할 수 있다!
💡느낀 점
문제를 보면서 bfs 탐색을 사용해야겠다는 생각은 하였으나, 레버의 위치까지 갔다가 도착점까지 가야한다는 생각에 코드를 어렵게만 생각하고 있었다. 그냥 단순하게 bfs 탐색 2번을 진행하면 되는 문제여서 bfs 탐색의 코드에 대한 이해만 있다면 손쉽게 풀 수 있는 문제였다. 물론 나는 어렵게 생각해서 이상한 길로 빠질 뻔했다가 돌아왔다..
링크
