알고리즘 : BFS (2) 실습! 코딩테스트 풀이 도전

내가 풀어볼 BFS 코테는 프로그래머스의 '게임 맵 최단거리'이다.

우선 문제를 읽어보면 캐릭터는 이차원 배열의 0,0에 위치하고, 진영은 n-1, m-1에 위치한다.

(이차원 배열의 크기를 [n][m]으로 가정 시)

 

즉, 왼쪽 위와 오른쪽 아래에 각각 위치하기 때문에 캐릭터는 최단으로 이동하려면 오른쪽과 아래로만 이동하는 것이 좋다.

물론 길이 왼쪽이나 위밖에 없다면 그 경우도 고려하게 되겠지만.

 

어쨌든 풀이를 시작해보자!

프로그래머스

 

---

 

먼저 나는 크기가 똑같은 boolean 타입 이차원 배열 하나를 생성해주기로 결심했다.

queue를 통해 반복문을 돌며 캐릭터가 길을 지나갈때, 지나온 길인지 체크할 용도이다.

 

다음 내가 사용할 로직은 아래와 같다.

• 오른쪽 길이 벽인지 확인하고 벽이 아니라면 이동한다.
• 아래쪽 길이 벽인지 확인하고 벽이 아니라면 이동한다.
• 왼쪽 길이 벽인지 확인하고 벽이 아니라면 이동한다.
• 위쪽 길이 벽인지 확인하고 벽이 아니라면 이동한다.
• 이동하다가 벽을 만나서 도착하지 못 하면 이전으로 돌아가서 위 로직을 다시 실행한다.

벽이 아니라면 이동하도록 하는 알고리즘만 코드로 작성한 결과이다. [약 20분 소요🔥]

(이동하다가 벽을 만나서 도착하지 못 한 경우 예외 처리 X 상태)

import java.util.*;
class Solution {
    	static Queue<int[]> queue;
	static int[][] map;
	static boolean[][] check;
	static int cnt=1;
	
	public static boolean pushToQ(int x, int y) {
		if(!check[x][y]) {
			if(map[x][y]==1) {
				queue.add(new int[] {x, y});
				check[x][y]=true;
				cnt++;
				return true;
			} return false;
		} return false;
	}
    
    	public int solution(int[][] maps) {
        	map=maps;
		int n=maps.length-1;
		int m=maps[0].length-1;
		check=new boolean[n+1][m+1];
		check[0][0]=true;
		
		queue=new LinkedList<>();
		queue.add(new int[] {0, 0});
		int x=0, y=0;
		
		while(x!=n || y!=m) {
			int[] loc=queue.poll();
			x=loc[0];
			y=loc[1];
			if(x==n && y==m) break;
			if(y!=m) if(pushToQ(x, y+1)) continue;
			if(x!=n) if(pushToQ(x+1, y)) continue;
			if(y!=0) if(pushToQ(x, y-1)) continue;
			if(x!=0) if(pushToQ(x-1, y)) continue;
			if(queue.isEmpty()) {
				cnt=-1;
				break;
			}
		}
        	return cnt;
    	}
}

 

당연히 예외사항이 있으므로 틀릴 것은 예상했지만, 생각보다 많이 안 틀려서 신기.

 

---

 

그리고 ...

풀다가 포기하고.. 이어서 다음날 다시 풀기 시작했다.

BFS에 원리에 대한 이해를 먼저 다시 제대로 하기루 결심 ㅠ0ㅠ..

 

우선 BFS는

while(!queue.isEmpty()) {

     String root=queue.poll();

     for( ) {

          // root와 인접한 node들 조회

     }

}

이러한 원리이다. 그림을 그리며 생각하니 잘 이해가 됐다.

이 원리를 이해하고 문제를 다시 풀어보니 풀리기 시작..!! 🥹 그저 감격.

 

첫 번째 도전은 이러하다.

import java.util.*;
class Solution {
    static Queue<int[]> queue;
	static boolean[][] check;
	static int cnt=1;

	public int solution(int[][] maps) {
		int n=maps.length-1;
		int m=maps[0].length-1;
		check=new boolean[n+1][m+1];
		check[0][0]=true;
		
		queue=new LinkedList<>();
		queue.add(new int[] {0, 0});
		int x=0, y=0;
		
		while(!queue.isEmpty()) {
			int[] root=queue.poll();
			x=root[0];
			y=root[1];
			if(x==n && y==m) return cnt;
			int[][] nodes={{x+1, y},{x, y+1},{x-1, y},{x, y-1}};
			for(int i=0;i<nodes.length;i++) {
				int row=nodes[i][0];
				int cal=nodes[i][1];
				if(row>=0 && row<=n && cal>=0 && cal<=m) {
					if(maps[row][cal]==1) {
						if(!check[row][cal]) {
							queue.add(nodes[i]);
							check[row][cal]=true;
							cnt++;
							break;
						}
					}
				}
			}
		}
		
        return -1;
	}
}

 

(전보다 낮은 점수 :: 🤣 ㅋㅋ)

이제 문제는 cnt를 구할때 여러 경로를 탐색하게 되는데,

어떤 경로로 가느냐에 따라 cnt가 다르게 저장되어야한다, 는 것.

그래서 queue에 저장하는 것을 다르게 설정했다. 기존에 x, y (행의 인덱스, 열의 인덱스)를 저장했다면

거기에 추가로 cnt (이 경로로 지나가는 길의 현재 길이)를 함께 queue에 넣어주었다.

그렇게 코드를 수정했고..

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
		int n=maps.length-1;
		int m=maps[0].length-1;
		
		Queue<int[]> queue=new LinkedList<>();
		queue.add(new int[] {0, 0, 0});
		int x=0, y=0, cnt=1;
		
		while(!queue.isEmpty()) {
			int[] root=queue.poll();
			x=root[0];
			y=root[1];
			cnt=root[2];
			
			if(x==n && y==m) return cnt+1;
			int[][] nodes={{x+1, y, cnt},{x, y+1, cnt},{x-1, y, cnt},{x, y-1, cnt}};
			
			for(int i=0;i<nodes.length;i++) {
				int row=nodes[i][0];
				int cal=nodes[i][1];
				int tmp=cnt;
				if(row<0 || row>n || cal<0 || cal>m) continue;
				if(maps[row][cal]==0) continue;
				queue.add(new int[] {row, cal, tmp+1});
				maps[row][cal]=0;
			}
		}
        return -1;
	}
}

 

해결 !!!

이렇게 오래 한 문제를 머리쓰며 한 것은 처음인 것 같다..

마음이 아프긴 하지만 그만큼 뿌듯하다 !!

어려운 문제를 푸는 것 만큼 큰 쾌감은 없는 듯 😎