[programmers] 미로 탈출

문제
https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

---

< 미로 탈출 >

 

문제 풀이 (Java)

import java.util.*;

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

		char arr[][] = new char[maps.length][maps[0].length()];
		int s[] = new int[2];
		int l[] = new int[2];
		int e[] = new int[2];

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

		int move1 = bfs(l, s, arr);
		int move2 = bfs(l, e, arr);

		if (move1 != -1 && move2 != -1) {
			answer = move1 + move2;
		}

		return answer;
	}

	private int bfs(int[] start, int[] end, char[][] arr) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { start[0], start[1], 0 });

		int dx[] = { -1, 1, 0, 0 };
		int dy[] = { 0, 0, -1, 1 };

		boolean[][] visited = new boolean[arr.length][arr[0].length];
		visited[start[0]][start[1]] = true;

		while (!queue.isEmpty()) {
			int info[] = queue.poll();

			for (int i = 0; i < 4; i++) {
				int x = info[0] + dx[i];
				int y = info[1] + dy[i];

				if (x == end[0] && y == end[1]) {
					return info[2] + 1;
				}

				if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && arr[x][y] != 'X' && !visited[x][y]) {
					queue.add(new int[] { x, y, info[2] + 1 });
					visited[x][y] = true;
				}
			}

		}
		return -1;

	}
}

 

먼저 maps를 이차원 배열로 바꿔주며 시작 지점, 출구, 레버 위치를 구한다. (레버->시작)까지 걸리는 시간과 (레버->도착)까지 걸리는 시간을 bfs로 구한다. 이때, 둘 중 하나라도 -1이 반환되었다면 탈출할 수 없는 것이므로 최종 -1을 반환하고, 둘 다 -1이 아니라면 최종 두 값을 더해 반환한다.

 

bfs 함수에서는 Queue에 레버 위치와 이동 시간 0을 저장하고 현재 위치를 방문표시 한다. Queue가 빌 때까지 다음 과정을 반복한다.

1. queue poll

2. 상, 하, 좌, 우를 탐색하며 배열 범위 안이고, 벽이 아니고, 아직 방문하지 않은 곳이라면 Queue에 저장 및 방문표시 한다. 이때, 도착 위치에 도달했다면 걸린 시간을 반환한다.

모든 탐색을 마친 뒤 도착 위치에 도달하지 못한다면 -1을 반환한다.

 

---

⭐중간에 거쳐야 하는 곳이 있다면 (중간 위치 -> 시작 위치) + (중간 위치 -> 도착 위치)를 구하면 쉽게 구할 수 있다! ⭐

까먹지 말기..!

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges