문제 링크
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
리코쳇 로봇이라는 보드게임이 있습니다.
이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.
다음은 보드게임판을 나타낸 예시입니다.
...D..R
.D.G...
....D.D
D....D.
..D....여기서 "." 은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 멈춰 설 수 있으며, 이것이 최소 움직임 중 하나입니다.
게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return하는 solution 함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.
제한사항
- 3 ≤ board의 길이 ≤ 100
- 3 ≤ board의 원소의 길이 ≤ 100
- board의 원소의 길이는 모두 동일합니다.
- 문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
- "R"과 "G"는 한 번씩 등장합니다.
입출력 예
| board | result |
| ["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."] | 7 |
| [".D.R", "....", ".G..", "...D"] | -1 |
문제 풀이
[고려사항]
시작 위치부터 목표 위치까지 모든 경로 중 최소 움직임을 찾아야한다.
board의 최대 크기는 100 * 100(10,000)이므로, 모든 가능한 경로를 탐색하는 방식으로 구현한다면 시간을 초과한다.
그래서 최단 거리를 찾는 알고리즘으로 BFS를 이용해서 구현한다.
BFS로 구현할 경우에는, 모든 노드를 4방향으로 방문하기 때문에 최악의 경우라도, O(10,000)이 된다.
[알고리즘, 구현방법]
최단 경로를 찾는 문제이므로 BFS를 이용해서 구현했다.
여기서 말의 움직임은 장애물(D)이나 보드의 맨 끝에 부딪힐 때까지 미끄러지는 것이다.
일반적인 BFS와 다른점은 이동하는 칸의 개수가 한 칸이 아니라, 장애물이나 벽에 부딪힐 때까지 최대한 갈 수 있는 n칸을 이동한다는 것이다.
즉, 상하좌우의 방향 중 한 칸만 움직이는것이 아니라 특정 방향으로 최대한 갈 수 있는 칸을 구해야한다.
그래서 BFS 방문 배열을 boolean이 아니라 int 로 선언해서 해당 지점까지의 이동 횟수를 저장했다.
[풀이 과정]
*자세한건 코드내에 주석을 확인하면서 따라가주세요!
1. 시작 위치 찾기(R)
2. 시작 위치를 Queue에 저장하고 BFS 수행
- 4방향에 대해 BFS 수행
- 한 방향에 대해 최대한 갈 수 있는 만큼 이동
- 벽이나 장애물에 부딪힌 경우, 벽이나 장애물을 부딪히기 전 좌표로 돌아와서, 해당 지점까지의 이동 횟수 저장하고 Queue에 저장하여 해당 지점부터 탐색
- 현재 지점이 목표 위치(G)라면 이동 횟수 answer에 저장하고 Break;
정답 코드
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int solution(String[] board) {
int row = board.length;
int col = board[0].length();
int[][] cnt = new int[row][col];
// 1. 시작 위치(R) 찾기
Queue<Point> q = new LinkedList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i].charAt(j) == 'R') {
q.add(new Point(i, j));
cnt[i][j] = 1;
break;
}
}
}
// 2. BFS 탐색
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
int answer = -1; // 목표위치에 도달할 수 없다면 -1을 return
while (!q.isEmpty()) {
Point current = q.poll();
// 현재 지점이 목표 위치인지
if (board[current.x].charAt(current.y) == 'G') {
answer = cnt[current.x][current.y] - 1; // 시작 위치를 1로 초기화 했으므로, 이동 횟수는 -1
break;
}
// 4방향에 대해 BFS를 수행
for (int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
// 해당 방향으로 최대한 이동
while (true) {
if ((nx >= 0 && nx < row && ny >= 0 && ny < col) && board[nx].charAt(ny) != 'D') {
nx += dx[i];
ny += dy[i];
} else { // 벽이나 장애물에 부딪힌 경우
nx -= dx[i];
ny -= dy[i];
break;
}
}
// 최대한 움직인 지점을 방문한 적이 없으면, 해당 지점에서 탐색
if (cnt[nx][ny] == 0) {
q.add(new Point(nx, ny));
cnt[nx][ny] = cnt[current.x][current.y] + 1; // 현재 탐색을 시작한 위치에서 이동 횟수 +1
}
}
}
return answer;
}
public class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}'⚒️ Coding Test' 카테고리의 다른 글
| [백준] 인구 이동 - 자바(Java) (0) | 2024.08.22 |
|---|---|
| [프로그래머스] [PCCP 기출문제] 2번 / 석유 시추 - 자바(Java) (0) | 2024.08.10 |
| [백준] 탑 - 자바(Java) (0) | 2024.08.06 |
| [백준] 1, 2, 3 더하기 4 - 자바(Java) (0) | 2024.08.01 |
| [백준] 겹치는 건 싫어 - 자바(Java) (0) | 2024.07.31 |
