[프로그래머스] 미로 탈출 - JAVA

[프로그래머스] 코딩테스트 연습 > 연습문제 > 미로 탈출

문제 설명

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

---

풀이

bfs를 사용해서
시작 지점에서 레버까지, 레버에서 출구까지 최단 경로를 구하였다.

코드

import java.util.*;

class Node {
	int x, y, cnt;

	Node(int x, int y) {
		this.x = x;
		this.y = y;
		this.cnt = 0;
	}

	Node(int x, int y, int cnt) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}
}

class Solution {
    public int solution(String[] maps) {
        int answer = 0;

		Node s = null, l = null, e = null;
		for (int i = 0; i < maps.length; i++) {
			for (int j = 0; j < maps[0].length(); j++) {
				if (maps[i].charAt(j) == 'S') {
					s = new Node(i, j);
				} else if (maps[i].charAt(j) == 'L') {
					l = new Node(i, j);
				} else if (maps[i].charAt(j) == 'E') {
					e = new Node(i, j);
				}
			}
		}

		int cnt;
		
		cnt = bfs(maps, s, l);
		if(cnt == 0) return -1;
		answer+=cnt;
		
		cnt = bfs(maps, l, e);
		if(cnt == 0) return -1;
		answer+=cnt;

		return answer;
    }
    
    public int bfs(String[] maps, Node start, Node end) {
        int[] x = { 1, -1, 0, 0 };
		int[] y = { 0, 0, 1, -1 };

		LinkedList<Node> queue = new LinkedList<>();
		boolean[][] check = new boolean[maps.length][maps[0].length()];
		
		queue.add(start);
		check[start.x][start.y] = true;

		while (queue.size() != 0) {
			Node node = queue.poll();

			if (node.x == end.x && node.y == end.y) {
				return node.cnt;
			}

			for (int i = 0; i < 4; i++) {
				int nextx = node.x + x[i];
				int nexty = node.y + y[i];
				int nextcnt = node.cnt + 1;

				if (nextx >= 0 && nexty >= 0 && nextx < maps.length && nexty < maps[0].length()) {
					if (!check[nextx][nexty] && maps[nextx].charAt(nexty) != 'X') {
						queue.add(new Node(nextx, nexty, nextcnt));
						check[nextx][nexty] = true;
					}
				}
			}
		}
		return 0;
    }
}