https://school.programmers.co.kr/learn/courses/30/lessons/159993
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입력
문자열 배열 maps는 미로의 정보를 담고 있으며 각 문자는 한 칸을 의미
'S'는 시작점, 'L'은 레버, 'E'는 도착점, 'O'는 빈칸, 'X'는 벽을 의미
핵심 아이디어
미로에서 S → L → E 순서로 이동할 수 있는 최단 경로를 각각의 BFS로 계산
시작점에서 레버까지, 레버에서 도착점까지 두 번의 경로 탐색 수행
각 경로가 존재하지 않으면 -1을 반환
두 경로가 모두 존재하는 경우 각각의 거리 합에 시작점과 레버, 레버와 도착점 간 이동을 포함해 총 거리 계산
변수설명
dx, dy는 4방향 이동을 위한 좌표 변화량
map은 문자열 배열 maps를 2차원 문자열 배열로 변환한 맵 정보
start, lever, end는 각각 S, L, E의 좌표를 담은 정수 배열
q는 BFS에 사용되는 탐색 큐
distance는 방문 여부 및 이동 거리를 기록하는 2차원 정수 배열
curX, curY는 현재 탐색 중인 좌표
newX, newY는 이동 후 좌표
예시
maps가 ["SOO", "OXL", "OEO"]인 경우
S에서 L까지의 최단 거리 2
L에서 E까지의 최단 거리 2
총 경로는 존재하며 이동 횟수는 2 + 2 + 2 = 6
결과는 6
정답코드
import java.util.*;
class Solution {
static int[] dx = {0, 0 ,1, -1};
static int[] dy = {1, -1, 0, 0};
public int solution(String[] maps) {
int answer = 0;
String[][] map = new String[maps.length][maps[0].length()];
int[] start = new int[2];
int[] lever = new int[2];
int[] end = new int[2];
// String[] 배열을 map으로
for(int i=0; i<maps.length;i++){
for (int j = 0; j < maps[i].length(); j++) {
char ch = maps[i].charAt(j);
if(ch == 'S'){
map[i][j] = "S";
start[0] = i;
start[1] = j;
} else if(ch == 'L'){
map[i][j] = "L";
lever[0] = i;
lever[1] = j;
} else if(ch == 'E'){
map[i][j] = "E";
end[0] = i;
end[1] = j;
}
else if(ch == 'X')
map[i][j] = "X";
else if(ch == 'O')
map[i][j] = "O";
}
}
int a = bfs(map, start, lever);
int b = bfs(map, lever, end);
if(a != -1 && b != -1)
return a+b+2;
else return -1;
}
public int bfs(String[][] map, int[] start, int[] end){
int n = map.length;
int m = map[0].length;
// bfs 사용을 위한 큐
Queue<int[]> q = new LinkedList<>();
// 방문 노드 체크
int[][] distance = new int[map.length][map[0].length];
for(int[] v : distance)
Arrays.fill(v, -1);
int curX = start[0];
int curY = start[1];
// q에 시작값 삽입
q.add(new int[]{curX, curY});
// 반복
while(!q.isEmpty()){
System.out.println(q.size());
int[] now = q.poll();
curX = now[0];
curY = now[1];
// 목적지 도착
if (curX == end[0] && curY == end[1]) {
return distance[curX][curY];
}
// 4방향 탐색
for(int i=0; i<4; i++){
int newX = curX+dx[i];
int newY = curY+dy[i];
// 미로 범위 바깥일 경우, 이미 방문한경우, 벽인경우 >> 무시
if (newX < 0 || newX >= n || newY < 0 || newY >= m || distance[newX][newY] > 0 || map[newX][newY].equals("X")) {
continue;
}
// 방문횟수 + 1
distance[newX][newY] = distance[curX][curY] + 1;
q.add(new int[]{newX, newY});
}
}
// 목적지까지 경로 없는경우 -1 return
return -1;
}
}
'코딩테스트 > 문제풀이' 카테고리의 다른 글
[프로그래머스] 조이스틱 Java (1) | 2025.07.05 |
---|---|
[프로그래머스] 지게차와 크레인 Java (0) | 2025.07.05 |
[프로그래머스] 게임 맵 최단거리 Java (0) | 2025.07.05 |
[프로그래머스] 서버 증설 횟수 Java (0) | 2025.07.05 |
[프로그래머스] 비밀코드 Java (0) | 2025.07.05 |