문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/159993
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
문제 핵심
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다.
미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.
문제 풀이법
-레버가있는곳 까지 최단거리를 구한다
레버까지 도착하지못하면 -1 리턴
레버에서 다시 출구까지 최단거리를구한다
출구까지 도착못하면 -1리턴
코드
public static int solution(String[] maps) {
String[][] map = new String[maps.length][maps[0].length()];
int[] start = new int[2];
int[] lever = new int[2];
int[] arriv = new int[2];
for (int i = 0; i < maps.length; i++) {
for (int j = 0; j < maps[i].length(); j++) {
map[i][j] = String.valueOf(maps[i].charAt(j));
if (map[i][j].equals("S")) {
start[0] = i;
start[1] = j;
} else if (map[i][j].equals("L")) {
lever[0] = i;
lever[1] = j;
} else if (map[i][j].equals("E")) {
arriv[0] = i;
arriv[1] = j;
}
}
}
Arrays.stream(map).forEach(row -> System.out.println(Arrays.toString(row)));
System.out.println(
"시작: " + Arrays.toString(start) + " 레버: " + Arrays.toString(lever) + " 도착: " + Arrays.toString(arriv));
int re=bfs(start, lever, map);
if(re==-1){
System.out.println("래버까지도달하지못함");
return -1;
}
int re2=bfs(lever, arriv, map);
if(re2==-1){
System.out.println("출구까지도달하지못함");
return -1;
}
re=re+re2;
System.out.println(re);
return re;
}
public static int bfs(int[] start,int[] arriv, String[][] map){
int re=-1;
int mw = map[0].length;
int mh = map.length;
boolean[][] visited = new boolean[map.length][map[0].length];
System.out.println("맵사이즈: " + mw + "," + mh);
Queue<Integer[]> queue = new LinkedList<>();
queue.offer(new Integer[] { start[0], start[1], 0 });
visited[start[0]][start[1]] = true;
printvisit(visited);
boolean arrive = false;
while (!queue.isEmpty()) {
System.out.println("위치 탐색 예정 큐" +
queue.stream()
.map(Arrays::toString)
.toList());
Integer[] index = queue.poll();
Integer wid = index[1];
Integer hig = index[0];
Integer count = index[2];
System.out.println("현재좌표: " + hig + "," + wid);
if (wid == arriv[1]&& hig == arriv[0]) {
System.out.println(count+"번쨰만에 출구 또착");
re = count;
arrive = true;
break;
}
Integer right = wid + 1;
Integer left = wid - 1;
Integer up = hig - 1;
Integer down = hig + 1;
System.out.println("전진예정좌표: 오른쪽(" + hig + "," + right + ") 왼쪽(" + hig + "," + left + ") 위(" + up + "," + wid
+ ") 아래(" + down + "," + wid + ")");
if (right <= mw - 1) {
System.out.println("오른쪽전진: " + hig + "," + right);
String flg = map[hig][right];
System.out.println("전진값: " + flg);
if (!flg.equals( "X") && !visited[hig][right]) {
System.out.println("O이므로 위치 저장가능");
visited[hig][right] = true;
printvisit(visited);
queue.offer(new Integer[] { hig, right, count + 1 });
}
}
if (left >= 0) {
System.out.println("왼쪽전진: " + hig + "," + left);
String flg = map[hig][left];
System.out.println("전진값: " + flg);
if (!flg.equals( "X") && !visited[hig][left]) {
System.out.println("O이므로 위치 저장가능");
visited[hig][left] = true;
printvisit(visited);
queue.offer(new Integer[] { hig, left, count + 1 });
}
}
if (up >= 0) {
System.out.println("위쪽전진: " + up + "," + wid);
String flg = map[up][wid];
System.out.println("전진값: " + flg);
if (!flg.equals( "X") && !visited[up][wid]) {
System.out.println("O이므로 위치 저장가능");
visited[up][wid] = true;
printvisit(visited);
queue.offer(new Integer[] { up, wid, count + 1 });
}
}
if (down <= mh - 1) {
System.out.println("아래쪽전진: " + down + "," + wid);
String flg = map[down][wid];
System.out.println("전진값: " + flg);
if (!flg.equals( "X") && !visited[down][wid]) {
System.out.println("O이므로 위치 저장가능");
visited[down][wid] = true;
printvisit(visited);
queue.offer(new Integer[] { down, wid, count + 1 });
}
}
}
if (!arrive) {
return -1;
}
return re;
}
public static void printvisit(boolean[][] visited) {
System.out.println("visited 생성 시작");
for (int i = 0; i < visited.length; i++) {
for (int ii = 0; ii < visited[i].length; ii++) {
System.out.print(visited[i][ii] + " ");
}
System.out.println();
}
System.out.println("visited 생성 종료");
}
결과
gpt피드백
-상하좌우 코드 중복이야. 지금 오른쪽/왼쪽/위/아래를 각각 if로 작성해서 BFS가 길어졌어.
배운점느낀점
-이전에 아주 비슷한 문제를 풀었었다
게임최단거리라고 그때bfs를 익혔었고
사용하면 될거같았다 근데 문제는 레버였다
그래서 첫구현은 출구 까지 가는 길에 레버를 체크하는건데
어려웠다 그래서 다시 곰곰히 생각했다.
그랬더니 그냥 도착지점을 두번 즉 bfs를 두번 돌리면 되는거였다
첫번쨰 출발지는 s 첫 도착지는 래버
두번째 출발지는 래버 두번째 도착지는 출구
즉 bfs 두번 호출해서 더하면 되는거였다
'코테 > lvl2' 카테고리의 다른 글
| 프로그래머스 호텔 대실(lvl2) 풀어보기 (0) | 2026.09.17 |
|---|---|
| 프로그래머스 리코쳇 로봇(lvl2) 풀어보기 (0) | 2026.09.17 |
| 프로그래머스 거리두기 확인하기(lvl2) 풀어보기 (0) | 2026.09.15 |
| 프로그래머스 메뉴 리뉴얼(lvl2) 풀어보기 (0) | 2026.09.15 |
| 프로그래머스 후보키(lvl2)풀어보기 (0) | 2026.09.15 |