문제:
진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다.
칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다.
매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고,
그 방향으로 최소 1개, 최대 K개의 빈 칸을 이동한다.
첫째 줄에 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K가 주어진다.
둘째 줄부터 N개의 줄에는 체육관의 상태가 주어진다.
체육관의 각 칸은 빈 칸 또는 벽이고, 빈 칸은 '.', 벽은 '#'으로 주어진다.
마지막 줄에는 네 정수 x1, y1, x2, y2가 주어진다. 두 칸은 서로 다른 칸이고, 항상 빈 칸이다.
(x1, y1)에서 (x2, y2)로 이동하는 최소 시간을 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.
풀이:
출발지(x1, y1)에서 목적지(x2, y2)까지 가려면, 어떤 지점 Sn들을 지나야 할 것이다.
이때, 어떤 지점 Sn까지 가는데 최소 시간Tn이 걸릴 것이고,
어떤 지점Sn에서 다음 지점Sn+1까지 가는데에는 Tn + 1초가 걸릴 것이다.
이를 BFS를 이용하여 풀면 각 시간별로 갈 수 있는 위치를 알 수 있을 것이고,
가장 처음 목적지(x2, y2)에 도착하면, 그 시간이 목적지까지 이동하는 최소 시간이 될 것이다.
위 조건에 맞는 코드를 작성하기 위해 아래와 같은 전역변수를 작성해주었다.
static int N, M, K;
static boolean[][] gym;
static int[][] visited;
static int x1, y1, x2, y2;
static int[] xMove = {1,-1,0,0};
static int[] yMove = {0,0,1,-1};
static int max = 999999999;- gym[][] 배열은 체육관의 생김새를 나타내며, 이동할 수 없는 벽은 false, 이동할 수 있는 경로는 true로 저장한다.
- visited[][] 배열은 출발지부터 해당 좌표까지 이동하는 최소 시간을 저장한다.
- xMove[], yMove[] 배열은 이동 방향을 나타낸다.
- max는 visited를 초기화 하기 위해 설정했다.
이후 아래와 같이 메인메서드에서 입력을 받아주고 이후 함수를 호출해준다.
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
gym = new boolean[N][M];
visited = new int[N][M];
for (int i = 0; i < N; i++) {
Arrays.fill(visited[i], max);
}
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
gym[i][j] = line.charAt(j) == '.';
}
}
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken()) - 1;
y1 = Integer.parseInt(st.nextToken()) - 1;
x2 = Integer.parseInt(st.nextToken()) - 1;
y2 = Integer.parseInt(st.nextToken()) - 1;
System.out.println(running());
}- gym[][]배열에 의해 벽은 false, 이동 가능 경로는 true로 저장된다.
- x1, y1, x2, y2는 1씩 빼줬는데, 문제에서는 (1,1)에서 지도가 시작하지만, 내가 작성한 체육관 지도는 (0,0)부터 시작하기 때문이다.
running()메서드는 아래와 같다.
static int running() {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x1, y1, 0});
visited[x1][y1] = 0;
while (!queue.isEmpty()) {
int[] now = queue.poll();
int nowX = now[0];
int nowY = now[1];
int time = now[2];
if (nowX == x2 && nowY == y2) {
return time;
}
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= K; j++) {
int nextX = nowX + xMove[i] * j;
int nextY = nowY + yMove[i] * j;
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M
|| !gym[nextX][nextY] || visited[nextX][nextY] < time + 1) {
break;
}
if (visited[nextX][nextY] == max) {
queue.add(new int[]{nextX, nextY, time+1});
visited[nextX][nextY] = time+1;
}
}
}
}
return -1;
}- BFS 문제이니, queue를 이용해준다.
queue에는 지금 위치의 x, y좌표, 출발지로부터 몇초 뒤에 도착했는지 배열의 형태로 저장된다.
visited에는 위에서 설명한 바와 같이 출발지로부터 해당 위치까지 가는데 걸리는 최소 시간이 저장된다. - 큐에 저장된 위치, 시간 정보를 가져온다.
각각 nowX, nowY, time에 저장해놓는다. - 만일 지금 위치가 목적지라면, time을 반환해주며, 메서드가 종료된다.
BFS를 이용한 풀이이므로 어떤 위치에 가장 먼저 도착하면, 시간은 무조건 최소 시간이다. - 한방향으로 K범위에서 자유롭게 이동할 수 있다. xMove와 yMove를 이용하여 각 방향으로 차례로 이동해준다.
- j는 1~K까지 증가한다. 다음 위치로 가능한 좌표는 아래와 같다.
nextX = nowX + xMove[i] * j;
nextY = nowY + yMove[i] * j; - 각 좌표가 지도를 벗어났는지 검사한다.
- 각 좌표가 벽에 도달했는지 검사한다.
- 각 좌표에 현 시간(time) + 1보다 작은 값이 저장되어 있는지 검사한다.
4번을 하는 이유는, 중복을 줄이기 위해서이다. 아래의 예시를 보자.
지금 노랗게 표시되어 있는 위치의 오른쪽을 검사한다고 생각해보자.
01 1 1 벽 2 2 2 2 2 2 2 2 2 도착
이미 큐에 해당 좌표에 대한 정보가 저장 되어 있을 것이고, 그게 더 나은 방법일 것이다.
고로 굳이 검사할 필요가 없고, 이로 인해 중복을 줄일 수 있다.
또한 그 넘어서도 확인할 필요가 없는데, 다음 좌표에서 가나, 지금 좌표에서 가나 시간 차이가 없고,
다음 좌표에서 갈 때, 더 멀리 갈 수 있기 때문이다.
아래 그림과 같이 첫번째에서는 1칸밖에 더 못보지만, 두번째 위치에서는 2칸이나 더 볼 수 있다.
0 1 1 0 1 1 벽 2 2 벽 2 2 2 2 2 2 - 만일 2, 3, 4번중 하나라도 조건에 만족하지 않으면 반복문을 마친다.
굳이 더 가볼 필요가 없기 때문이다. - 만일 다음 좌표가 초기화된 상태 그대로라면, 큐에 다음 좌표의 정보와 지금 시간 + 1을 저장해준다.
- j는 1~K까지 증가한다. 다음 위치로 가능한 좌표는 아래와 같다.
- 큐가 빌 동안 2번 ~ 4번 과정을 반복한다.
만일 큐가 빌 동안 반환이 일어나지 않는다면, 도달할 수 없다는 말이니 -1을 반환한다.
전체코드:
import java.io.*;
import java.util.*;
public class 달리기_16930번 {
static int N, M, K;
static boolean[][] gym;
static int[][] visited;
static int x1, y1, x2, y2;
static int[] xMove = {1,-1,0,0};
static int[] yMove = {0,0,1,-1};
static int max = 999999999;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
gym = new boolean[N][M];
visited = new int[N][M];
for (int i = 0; i < N; i++) {
Arrays.fill(visited[i], max);
}
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
gym[i][j] = line.charAt(j) == '.';
}
}
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken()) - 1;
y1 = Integer.parseInt(st.nextToken()) - 1;
x2 = Integer.parseInt(st.nextToken()) - 1;
y2 = Integer.parseInt(st.nextToken()) - 1;
System.out.println(running());
}
static int running() {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x1, y1, 0});
visited[x1][y1] = 0;
while (!queue.isEmpty()) {
int[] now = queue.poll();
int nowX = now[0];
int nowY = now[1];
int time = now[2];
if (nowX == x2 && nowY == y2) {
return time;
}
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= K; j++) {
int nextX = nowX + xMove[i] * j;
int nextY = nowY + yMove[i] * j;
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M
|| !gym[nextX][nextY] || visited[nextX][nextY] < time + 1) {
break;
}
if (visited[nextX][nextY] == max) {
queue.add(new int[]{nextX, nextY, time+1});
visited[nextX][nextY] = time+1;
}
}
}
}
return -1;
}
}
시행착오:
- visited를 for문 밖에서 큐에서 지금 위치를 꺼낼 때 갱신 시켜버렸다.그 결과 중복이 발생해 시간 초과가 발생했다
- 더보기
public class 달리기_16930번_시간초과 { static int N, M, K; static boolean[][] gym; static int x1, y1, x2, y2; static int[] xMove = {1,-1,0,0}; static int[] yMove = {0,0,1,-1}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); gym = new boolean[N][M]; for (int i = 0; i < N; i++) { String line = br.readLine(); for (int j = 0; j < M; j++) { gym[i][j] = line.charAt(j) == '.'; } } st = new StringTokenizer(br.readLine()); x1 = Integer.parseInt(st.nextToken()); y1 = Integer.parseInt(st.nextToken()); x2 = Integer.parseInt(st.nextToken()); y2 = Integer.parseInt(st.nextToken()); System.out.println(running()); } static int running() { Queue<int[]> queue = new LinkedList<>(); queue.add(new int[]{x1-1, y1-1, 0}); while (!queue.isEmpty()) { int[] now = queue.poll(); int nowX = now[0]; int nowY = now[1]; int time = now[2]; gym[nowX][nowY] = false; if (nowX == x2-1 && nowY == y2-1) { return time; } for (int i = 0; i < 4; i++) { for (int j = 1; j <= K; j++) { int nextX = nowX + xMove[i] * j; int nextY = nowY + yMove[i] * j; if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && gym[nextX][nextY]) { queue.add(new int[]{nextX, nextY, time+1}); } else { break; } } } } return -1; } } - max 값을 실수로 Integer.MIN으로 작성했다.
tab 키가 불러온 참사였고, 덕분에 max 말고 맞는 코드를 어디가 틀린지 한참 봐야했다.
디버깅 과정중에 visited[][]에 음수가 저장되는걸 발견했고, 코드를 수정할 수 있었다.
'알고리즘 > 백준' 카테고리의 다른 글
| 15989번 - dp, 규칙찾기 (0) | 2024.08.08 |
|---|---|
| 15486 - 퇴사2(dp) (0) | 2024.08.07 |
| 17086번 - 아기상어2(BFS, 8방향 탐색) (0) | 2024.08.04 |
| 14226번 - 이모티콘(bfs) (0) | 2024.07.31 |
| 13913번 - 숨바꼭질4(bfs) (0) | 2024.07.30 |
