문제
코드
import java.util.*;
class Node{
int r,c,distance;
Node(int r,int c, int distance){
this.r=r;
this.c=c;
this.distance=distance;
}
}
class Solution {
static Queue<Node> queue=new LinkedList<>();
static boolean[][] visited;
static Node findNode;
public int solution(String[] maps) {
for(int i=0;i<maps.length;i++){
boolean isFindStart=false;
for(int j=0;j<maps[0].length();j++){
if(maps[i].charAt(j)=='S'){
visited=new boolean[maps.length][maps[0].length()];
queue.add(new Node(i,j,0));
bfs('L',maps);
if(findNode.distance==-1) return -1;
isFindStart=true;
break;
}
}
if(isFindStart) break;
}
visited=new boolean[maps.length][maps[0].length()];
queue=new LinkedList<>();
queue.add(findNode);
bfs('E',maps);
return findNode.distance;
}
public static void bfs(char search,String[] maps){
while(!queue.isEmpty()){
Node node=queue.poll();
visited[node.r][node.c]=true;
if(maps[node.r].charAt(node.c)==search){
findNode=node;
return;
}
if(node.r>0&&!visited[node.r-1][node.c]&&maps[node.r-1].charAt(node.c)!='X'){
queue.add(new Node(node.r-1,node.c,node.distance+1));
visited[node.r-1][node.c]=true;
}
if(node.r<maps.length-1&&!visited[node.r+1][node.c]&&maps[node.r+1].charAt(node.c)!='X'){
queue.add(new Node(node.r+1,node.c,node.distance+1));
visited[node.r+1][node.c]=true;
}
if(node.c>0&&!visited[node.r][node.c-1]&&maps[node.r].charAt(node.c-1)!='X'){
queue.add(new Node(node.r,node.c-1,node.distance+1));
visited[node.r][node.c-1]=true;
}
if(node.c<maps[0].length()-1&&!visited[node.r][node.c+1]&&maps[node.r].charAt(node.c+1)!='X'){
queue.add(new Node(node.r,node.c+1,node.distance+1));
visited[node.r][node.c+1]=true;
}
}
findNode=new Node(-1,-1,-1);
}
} 풀이
(1) 시작점을 찾기 위해 maps를 순회한다. 'S'를 찾으면 레버를 찾기위한 bfs 탐색을 시작한다.
(2) bfs() 함수에서는 bfs 알고리즘 방식으로 방문 노드를 큐에 넣고, visited 배열에 체크를 해주는 과정을 더 이상 큐에서 빼낼 노드가 없을 떄까지 반복한다.
(3) 만약 (2)의 과정에서 레버를 찾는다면, 레버의 좌표와 거리 정보가 저장된 노드를 저장하고, bfs() 함수를 종료한다. 모든 탐색이 종료될 때까지 레버를 찾지 못한다면 거리는 -1이 되고, 함수를 종료한다.
(4) 레버를 찾았다면, 이제 같은 방법으로 레버 노드를 시작점으로 하여 출구를 찾는 bfs 탐색을 시작한다. 이 과정은 위과 동일 하다.
(5) 출구를 찾지 못했다면 -1을 반환하고, 출구를 찾았다면, 출구 노드의 거리를 반환하여 준다.
결과
정말정말 고생을 많이 했던 문제이다.
사실 나는 dfs문제만 풀어봤지, bfs문제는 처음이다.
당연히 이 문제도 dfs로 풀 수 있을거라 생각했다. 그리고 기계적으로 dfs를 구현했는데, 시간 초과가 났다.
여기저기 찾아보니, 이런 최단 경로 문제는 bfs로 푸는 것이 바람직하다는 사실을 알 수 있었다.
bfs 알고리즘을 공부할 겸 코드를 초기화하고 처음부터 다시 썼다.
이번엔 많은 테스트 케이스에서 런타임 에러가 떴다. 프로그래머스에서 제출을 했을 때 런타임 에러가 뜨면 어떤 이유인지 알 수가 없기 때문에 정말 스트레스 받았다.
그래서 다른 사람들의 코드와 비교하면서 뭐가 문젠지 계속해서 찾았다.
다른 정답 풀이와의 차이점은 내 코드는 bfs를 재귀로 구현했다는 것이다. 이 경우에는 탐색하는 맵의 범위가 크면 스택오버플로우를 일으킬 수 도있다고 한다.
그래서 while(!queue.isEmpty()) 반복문을 사용하여 다시 고쳤는데, 이번에는 또 시간초과가 났다.
눈알이 빠지도록 내 코드를 계속해서 읽었다.
문제는 내가 방문 노드를 체크 할 때, 큐에서 꺼낸 노드만 방문 처리를 해놓은 것이었다.
원래는 상하좌우를 확인해서 다음 노드를 큐에 추가할 때마다 방문 처리를 했어야 하는데, 그러지 않았기 때문에 이미 방문한 노드도 또 방문하는 경우가 생긴 것이다.
이 문제 하나로 정말 많이 배운 것 같다. 비록 이 문제를 하루 종일 풀었지만, 이런 식으로 하루를 보낸 것은 굉장히 큰 수확이다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges
