https://school.programmers.co.kr/learn/courses/30/lessons/159993
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는 데 걸리는 시간을 구하려 합니다.
미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해 주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.
문제 요약
문제를 요약하자면, 미로 출발 지점에서 빠져나가는 문을 열 수 있는 레버지점에 들렸다가 빠져나가는 문을 통해 미로를 나갈때 걸리는 최소 시간을 구하는 문제이다.
해설
해당 문제는 전형적인 탐색 문제이며, 최소 거리를 보장해야하는 전형적인 너비 우선 탐색(BFS) 문제라고 볼 수 있다.
물론, DFS로 풀어도 테스트는 통과할 수 있지만 BFS보다 효율이 좋지 못할 수 있다. 이 부분은 DFS 해설에서 설명하도록 하겠다!
이 문제에서 핵심은 Start에서 출발하여 Exit로 바로 가면 안 되고 우선 Lever로 갔다가 Lever에서 Exit로 가야 한다.
또한, 방문한 곳도 여러번 방문할 수 있다는 것이다.
그렇기 때문에, Start에서 Lever로 가는 거리 따로, Lever에서 Exit로 가는 거리 따로 구해주면 좋다.
BFS 풀이
왜 이문제가 BFS 인가? 라는 의문이 들 수 있다.
그건 바로 최소 거리를 보장하기 위해서 같은 깊이를 탐색해 나가는 BFS가 가장 적절하기 때문이다.
DFS보다 효율이 좋은 이유는 DFS 풀이에서 작성하도록 하겠다.
BFS 탐색 접근 방법은 아래와 같다.
1. Start 지점인 S의 위치와 Lever 위치인 L을 구해 놓는다.
2. S에서 L까지의 최소 거리(시간)을 구한다. 단, 도달할 수 없으면 -1을 return 해준다.
3. L에서 E까지의 최소 거리(시간)을 구한다. 단, 도달할 수 없으면 -1을 return 해준다.
4. 2번에서 구한 거리와 3번에서 구한 거리를 더해준다.
5. S에서 L까지 방문 기록 따로 L에서 E까지 방문 기록은 따로 관리하는 게 좋다.
이때, 갔던 곳은 또 방문할 수 있는데 왜 방문 기록을 남겨야 하는 이유는 어찌 되었든 간에 최소 거리를 위해 무의미한 재방문을 막기 위해서다.
다시 말하지만 다시 방문할 수 있는 것은 어디까지나 2번 계산 따로 3번 계산 따로 해야하기 때문이다.
BFS 코드
import java.util.*;
class Node{
int x;
int y;
int count;
public Node(int x, int y, int count){
this.x = x;
this.y = y;
this.count = count;
}
}
class Solution {
int[] X = {0,0,-1,1};
int[] Y = {1,-1,0,0};
//
public int solution(String[] maps) {
int[] start = getStartPosition('S',maps); // 시작(S) 지점의 좌표 반환
int[] lever = getStartPosition('L',maps); // 레버(L) 지점의 좌표 반환
int leverCount = bfs('L', start, maps); //bfs(목적지(레버), 출발지(시작지점), 맵)
if(leverCount == 0){
return -1;
}
int exitCount = bfs('E', lever, maps); //bfs(목적지(출구), 출발지(레버), 맵)
if(exitCount == 0){
return -1;
}
return leverCount+exitCount;
}
//
private int bfs(char find, int[] start, String[] maps){
Queue<Node> q = new LinkedList<>();
q.offer(new Node(start[0], start[1], 0)); // 출발지 Node(x좌표,y좌표,count)
boolean[][] visited = new boolean[maps.length][maps[0].length()];
visited[start[0]][start[1]] = true; // 처음 출발지점 방문처리 true
int answer = 0;
while(!q.isEmpty()){
Node cur = q.poll();
if(maps[cur.x].charAt(cur.y) == find){
if(answer == 0){
answer = cur.count;
}else{
answer = Math.min(answer, cur.count); //answer에 저장된 값과 현재 count값중 최소값을 answer에 저장
}
}
for(int i=0;i<4;i++){
//상하좌우 4번 탐색
int x = cur.x + X[i];
int y = cur.y + Y[i];
// 현재 x,y좌표가 음수 or map길이 이상 or 벽 or 방문한 좌표일 경우 건너뜀.
if(x<0 || y<0 || x>=maps.length || y>=maps[0].length()
|| maps[x].charAt(y) == 'X' || visited[x][y]){
continue;
}
//위의 예외상황이 아닐 경우 현재 좌표를 방문처리 해주고, 1칸 이동했으므로 cur.count를 +1 해준다
visited[x][y] = true;
q.offer(new Node(x, y, cur.count+1));
}
}
return answer;
}
//
private int[] getStartPosition(char find, String[] maps){ // find(목적지)의 좌표반환
for(int i=0;i<maps.length;i++){
for(int j=0;j<maps[i].length();j++){
if(maps[i].charAt(j) == find){
return new int[]{i,j};
}
}
}
return null; //찾고자 하는 목적지가 없을경우 null 반환
}
}
for(int i=0;i<maps.length;i++){
for(int j=0;j<maps[i].length();j++){
if(maps[i].charAt(j) == find){
return new int[]{i,j};
}
}
}
여기서 가장 걱정이 됐던 부분은 바로 2중 for-loop을 통해 좌표를 반환해주는 getStartPosition 함수의 성능 문제였다.
코테를 준비하면서 2중 for-loop을 쓸때, 성능테스트에서 통과하지 못하는 경우가 많았다.
그래서 한번 시간 복잡도를 계산해 보기로 했다.
5 <= maps <= 100 (세로)
5 <= maps[i] <= 100 (가로)
이중 for-loop의 경우 시간복잡도는 (d)와 같이 동일한 반복횟수를 가질경우 O(N^2)시간 복잡도를
(e)와 같이 다른 반복횟수를 가질경우 O(NM)의 시간 복잡도를 가진다. 아래 코드는 후자의 경우이므로 최대 연산횟수는 100*100 즉 10000번의 연산이 나올수 있다.
위의 표를 보면,
O(N)이 허용하는 연산횟수는 1,000만이므로 데이터의 개수가 1,000만 개 이하면 이 알고리즘은 사용해도 된다.
따라서, 10000만 이하인 10000번 연산이 나와 위의 for-loop을 사용하는데 아무 문제가 없었다.
만약 위 반복문이 아래와 같았다면 최악의 경우 약 100^100(100의100제곱)의 연산이 필요하게 돼 문제를 통과하지 못했을 것이다.
for(int i=0;i<maps.length;i++){
for(int j=0;j<maps.length;j++){
if(maps[i].charAt(j) == find){
return new int[]{i,j};
}
}
}DFS 풀이
해당 풀이는 DFS로 푸는것보다 무조건 BFS로 푸는 게 더 효율적이고 올바른 방법이다라고 말하는 게 아니다.
단지, 내가 생각했을때 이러한 이유로 DFS보다 BFS로 푸는 게 더 맞다는 것을 설명하기 위해 작성하는 것이다.
간단하게 DFS말고 BFS로 풀어야 하는 이유는 이렇다.
1. BFS는 최소거리를 보장하지만, DFS는 최소거리를 따로 기록해야 한다.
2. BFS는 최소 거리를 알기 위해 갔던 곳을 또 갈 필요가 없어 시간적으로 효율이 좋다.
3. DFS로 하게 되면 갔던 곳을 또 들려서 탐색을 해야 하기 때문에 시간이 BFS 탐색 보다 더 많은 시간이 든다.
--> 이것이 DFS에 backTracking 코드가 들어가는 이유이다.
조금 더 자세하게 설명해보겠다.
DFS로 탐색하는 할 때, 한 가지 BFS와 다르게 해야 하는 게 있다.
방문 기록을 boolean 배열을 사용하는 게 아니라 int 배열을 사용하여, 해당 위치에 최소 거리를 기록하고 최소 거리 보다 더 많은 거리가 접근하면 제외시키는 방식으로 해야 한다.
DFS 방문기록 : int 배열 / BFS 방문기록 : boolean 배열
이유는 위의 이미지를 살펴보자 위에서 a에서 f로 가는 최소 거리는 3이다.
만약 boolean 배열을 사용한다고 가정해 보자 만약 깊이 우선 탐색을 예시 1처럼 먼저 하게 되면 c와 e는 이미 방문한 기록이 있기 때문에 최소 거리는 5가 나오게 된다.
하지만, int 배열로 하여 각 구간마다 최소 거리를 기록하게 되면 예시 1에서 c의 최소거리는 2이지만 예시 2에서는 c의 최소거리가 1이 된다.
이처럼 최소 거리를 구할 수 있게 되는 것이다.
DFS로 했을 때 int 배열로 최소 거리를 기록하여 나아가는 게 BFS에서는 자동이라고 해야 하나 당연시되는 것이다 왜냐면 같은 깊이를 탐색하기 때문이다.
예시 이미지로 살펴보자 BFS는 1번을 먼저 탐색하고 그다음 2번을 탐색하고 3번을 탐색하여 최소 거리를 파악할 수 있다.
그렇기 때문에 BFS를 쓰는 게 더 올바르다고 생각한다.
DFS 코드
import java.util.Arrays;
import java.util.Stack;
class Solution {
int[] X = {0, 0, 1, -1};
int[] Y = {1, -1, 0, 0};
public int solution(String[] maps) {
int[] start = getStartPosition('S', maps);
int[] lever = getStartPosition('L', maps);
int leverCount = dfs('L', start, maps);
if (leverCount == 0) {
return -1;
}
int exitCount = dfs('E', lever, maps);
if (exitCount == 0) {
return -1;
}
return leverCount + exitCount;
}
private int dfs(char find, int[] start, String[] maps) {
int[][] visited = new int[maps.length][maps[0].length()];
for (int[] ints : visited) {
Arrays.fill(ints, maps.length * maps.length);
}
visited[start[0]][start[1]] = 0;
int answer = 0;
Stack<Node> st = new Stack<>();
st.push(new Node(start[0], start[1], answer));
while (!st.isEmpty()) {
Node cur = st.pop();
if (maps[cur.x].charAt(cur.y) == find) {
if (answer == 0) {
answer = cur.count;
} else {
answer = Math.min(answer, cur.count);
}
}
for (int i = 0; i < 4; i++) {
int x = cur.x + X[i];
int y = cur.y + Y[i];
int count = cur.count + 1;
if (x < 0 || x >= maps.length || y < 0 || y >= maps[0].length()
|| maps[x].charAt(y) == 'X' || count >= visited[x][y] ) {
continue;
}
st.push(new Node(x, y, Math.min(visited[x][y], count)));
visited[x][y] = Math.min(visited[x][y], count); } }
return answer;
}
private int[] getStartPosition(char find, String[] maps) {
for (int i = 0; i < maps.length; i++) {
for (int j = 0; j < maps[i].length(); j++) {
if (maps[i].charAt(j) == find) {
return new int[]{i, j};
}
}
}
return null;
}
}
class Node {
int x;
int y;
int count;
public Node(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
출처: https://tang25.tistory.com/entry/프로그래머스-미로-탈출-Lv2-JAVA-BFS엄탱 [엄탱 개발 블로그:티스토리]
'코딩테스트 > BFS & DFS' 카테고리의 다른 글
| [DFS] 혼자 놀기의 달인 (1) | 2024.04.02 |
|---|---|
| [BFS] 리코쳇 로봇 (0) | 2024.03.07 |
| [DFS] 광물캐기 (0) | 2024.02.29 |
| [BFS] 전력망을 둘로 나누기 (0) | 2024.02.20 |
| DFS / BFS (1) | 2024.01.22 |
