[Java] 깊이/너비 우선 탐색(DFS/BFS) - 게임 맵 최단거리 (Lv2)

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

프로그래머스

 

 

✔ 입출력 예시

게임 맵 최단거리 입출력 예시

 

 

💡 포인트

1️⃣ 최단거리를 구해야 하므로 BFS 알고리즘 활용

https://ichijeochi.tistory.com/43?category=1012068 

BFS (Breadth-First Search)

2️⃣ 현재 위치에서 갈 수 있는 곳을 탐색하기 위해 사방 탐색 진행 (배열 dr, dc 참고)
3️⃣ 도착하지 못하는 경우에는 -1 반환

 

 

❓ 풀이방법

1️⃣ BFS 함수에 필요한 변수들 넣기 (maps, 방문 배열 생성)

2️⃣ 해당 위치의 정보를 담을 class 생성(행 인덱스, 열 인덱스, 현재까지 지나온 칸의 수) & BFS 실행을 위한 Queue 생성

3️⃣ 처음 위치 정보 Queue에 담고 방문 배열에 방문 표시

4️⃣ Queue가 빌 때까지 반복문을 반복

5️⃣ Queue의 가장 첫 원소를 빼내어 해당 위치에서 전진할 수 있는 칸이 있는지 판별 후, 있다면 전진할 수 있는 칸의 정보

      Queue에 담기 👉 (새로운 칸의 행, 새로운 칸의 열, 이전 칸의 cnt + 1)

      이때, 전진할 수 있는 칸이 있는지 판별할 때는 반드시 새로운 행과 열의 인덱스들이 maps내에서 갈 수 있는 칸인지

      판별 후, 방문 여부 등을 판별해야 ArrayIndexOutOfBoundsException 발생 ❌

6️⃣ 반복문 진행 중 현재 뽑은 원소의 행과 열이 도착 지점과 같다면 정답변수에 현재 원소의 칸(cnt)의 값을 담기

7️⃣ 만약, 반복문이 종료되어도 도착지점에 도착하지 못했다면 -1 반환

 

 

✔ 소스코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution { // 게임 맵 최단거리

	public static void main(String[] args) {
//		int[][] maps = {{1,0,1,1,1}, {1,0,1,0,1}, {1,0,1,1,1}, {1,1,1,0,1}, {0,0,0,0,1}};
		int[][] maps = {{1,0,1,1,1}, {1,0,1,0,1}, {1,0,1,1,1}, {1,1,1,0,0}, {0,0,0,0,1}};

		System.out.println(solution(maps));
	}

	private static int solution(int[][] maps) {
		// 1. 최단거리를 구하기 위해 BFS 활용
		return bfs(maps, new boolean[maps.length][maps[0].length]);
	}

	static class Spot {  // Q에 담을 원소의 정보
		int x;  // 행 인덱스
		int y;  // 열 인덱스
		int cnt;  // 현재 위치까지 지나온 칸의 수
		public Spot(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	
	private static int bfs(int[][] maps, boolean[][] v) {
		boolean flag = false;  // 도착하지 못하는 경우를 위한 flag
		int answer = 0;  // 정답변수
		int[] dr = {-1, 1, 0, 0};  // 행인덱스 이동배열(상 하 좌 우)
		int[] dc = {0, 0, -1, 1};  // 열인덱스 이동배열(상 하 좌 우)
		
		// 2. BFS를 실행하기 위한 Queue 생성
		Queue<Spot> q = new LinkedList<>();
		// 3. 처음 위치의 인덱스 q에 삽입
		q.add(new Spot(0, 0, 1));
		// 3. 처음 위치 방문한 것으로 표시
		v[0][0] = true;
		
		while(!q.isEmpty()) {  // 4. q의 원소가 모두 없어질 때까지 반복
			Spot s = q.poll();
			
			// 6. q가 비어있지 않아도 목표위치에 도착했다면 해당 위치까지 지나온 칸의 개수 정답변수에 넣고 반복문 멈춤
			if(s.x == maps.length-1 && s.y == maps[0].length-1) {
				answer = s.cnt;
				flag = true;  // 도착했으므로 flag 변수 변경
				break;
			}
			
			for(int i=0; i<dr.length; i++) {
				int nr = s.x + dr[i];
				int nc = s.y + dc[i];
				if(0 <= nr && nr < maps.length && 0 <= nc && nc < maps[0].length && !v[nr][nc] && maps[nr][nc] == 1) {  
                // 5. 전진할 수 있는 칸이 있다면 q에 담기
					q.add(new Spot(nr, nc, s.cnt+1));
					v[nr][nc] = true;  // 5. 방문한 것으로 처리
				}
			}
		}
		
		if(!flag) {  // 7. 방문하지 못했다면
			return -1;
		}
		
		return answer;
	}
}

 

 

❗ 결과

    👉 테스트 통과

SSAFY때, 알고리즘 스터디를 진행하며 최단거리문제들을 대부분 BFS로 해결했던 것이 기억나 바로 BFS로 문제를 풀었다.

코드 제출 후 효율성 테스트까지 있는 것을 보고 DFS로 풀었다면 시간초과가 떠 문제를 다시 풀어야 하지 않았을까 하는 생각이...

오랜만에 도전한 BFS는 전보다는 오래걸렸지만 한번에 테스트를 통과할 수 있었던 문제였다 😁👍