[문제]
https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
문제 요약 : 원숭이는 출발지점에서 도착지점에 가야 하는데 인접 한 방향 (상하좌우- 8방향)로 이동하거나 문제에서 주어진 기회를 이용하여 만큼 말처럼 이동 (8방향 -체스의 나이트와 같은 이동 방식) 해서 움직여야 하는 문제. 가장 최소한의 동작 수를 구하는 문제이다.
[풀이 과정]
이 문제 풀이를 검색했을 때 주로 3차원 배열을 사용한 풀이 방법이 많아서 2차원 배열로도 풀 수 있는 방법을 설명하고자 한다.
[1. Class 구조]
먼저 쉽게 값들을 저장하기 위해 Info라는 class를 만들어 주었다.
그리고 map에는 말로 이동할 수 있는 남은 횟수를 저장할 것이다.
static class Info {
int r; //행 좌표
int c; // 열 좌표
int hores; //말로 이동할 수 있는 남은 기회
int move ; //움직인 횟수
public Info(int r, int c, int hores,int move) {
this.r=r;
this.c=c;
this.hores=hores;
this.move=move;
}
}
static int [][]map; // 말로 이동할 수 있는 남은 횟수를 저장함
//입력값
static int K;
static int R,C;
[2. map[][] 초기화]
문제에서 0이면 평지 , 1이면 장애물이다.
장애물일 때는 Integer.MAX_VALUE 값으로 초기화를 시켜주었다. 애초에 이 칸에 접근할 수 없도록 큰 값으로 초기화를 해주었다.
그리고 평지일 때는 -1로 초기화를 해주었다. 그 이유는 남은 말의 횟수가 0일 수도 있기 때문에 평지를 0으로 초기화시켜버리면 0인 모든 칸들이 말로 이동할 수 있는 남은 횟수가 0이라는 의미가 되어버리기 때문이다.
for(int i = 0 ; i <R ;i++){
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j<C;j++){
int n = Integer.parseInt(st.nextToken());
if(n==1){ //장애물일때
map[i][j] = Integer.MAX_VALUE;
}else {
//평지일때 -1로 초기화. -> 그 이유는 map에 남은 말처럼 이동할 수 있는 남은 횟수를 저장할꺼기 때문 따라서 0값도 올 수 있기때문에 -1로 초기화.
map[i][j] = -1;
}
}
}
[3 . BFS]
bfs 함수에서 큐에서 꺼낸 Info의 좌표에서 다음으로 이동할 좌표가 도착지점이라면 지금까지 이동한 횟수에 +1 한 값을 리턴하면 정답(최소 동작 수)이다.
큐에 들어가는 Info.move 의 값은 반드시 1,2,3,,,,이렇게 순차적으로 들어가기때문이다. 그래서 큐에서 꺼낸 좌표에서 다음 이동하는 좌표가 정답이라면 가장 최소 움직임의 값이 나올 수 밖에 없다.
그러면 방문처리는 어떻게 해주어야할까?
방문처리를 해주지 않으면 계속 무한루프를 돌테니 적절한 방문처리 조건이 필요하다.
한번 방문했다고 방문하지 않게 처리하는게 아닌, map[nr][nc]의 값이 curHourse (말처럼 이동할 수 있는 남은 횟수) 보다 작다면 다시한번 방문 할 수 있도록 처리하였다.
if(map[nr][nc]<curHourse)그 이유는 처음에 어떠한 좌표에 처음 도착했을때 (예 : (3,2) ) 에 map[3][2] 에 = 2를 저장하였다고 해보자.
map[3][2]까지 오는데 말처럼 이동할 수 있는 남은 횟수가 2라는 의미이다. 이때 2라는 값을 저장하고 방문을 했기때문에 이 좌표에 다시 들어오지 못하게끔 처리를 하면 안된다. 2라는 횟수를 이용하여 그 다음 이동할 수 있는 좌표를 또 큐에 담게 될텐데 , 이때 큐에 들어가는 좌표들이 정답인 도착지점에 도착한다는 보장이 없기때문에다.
따라서 2라는 값보다 더 큰 말처럼 이동할 수 있는 남은 횟수가 들어온다면 2보다 더 많은 경우로 다른 좌표에 이동해 볼 수 있기때문에 map[nr][nc]<curHourse 일때 다시 한번 방문 할 수 있도록 처리해 주어야한다.
/* 2차원 배열 안에 존재하는 좌표인지 판단하는 함수 */
private static boolean isRange (int r,int c){
return r>=0 && r<R && c>=0 && c<C;
}
private static int bfs (Info info) {
/* 인접( 상하좌우) (순서는 다름) */
int [] dr = {0,0,1,-1};
int [] dc = {1,-1,0,0};
/* 8방 체스의 나이트와 같음 */
int [] hr = {-1, 1, -1, 1, -2, 2, -2, 2};
int [] hc = {-2, -2, 2, 2, -1, -1, 1, 1};
Queue<Info> queue = new ArrayDeque<>();
queue.add(info);
/*시작지점과 도착지점이 같을 수 있는경우는 이동횟수는 0이기때문에 0을리턴 */
if (R == 1 && C== 1) return 0;
while (!queue.isEmpty()) {
Info current_Info = queue.poll();
int curR = current_Info.r;
int curC = current_Info.c;
int nextMove = current_Info.move +1;
int curHourse = current_Info.hores;
//상 하 좌 우 인접이동
for(int i = 0 ; i <4 ; i++){
int nr = curR + dr[i];
int nc = curC + dc[i];
//2차원 배열의 범위를 넘어가는 경우는 넘겨준다.
if (!isRange(nr, nc) )continue;
if(map[nr][nc]<curHourse){
if(nr==R-1 && nc ==C-1){
return nextMove;
}
//map에 남은 말처럼 이동 할 수 있는 횟수를 저장한다.
map[nr][nc] = curHourse;
queue.add(new Info(nr, nc, curHourse, nextMove));
}
}
//말처럼 이동 하는 경우
// 남은 횟수가 0보다 커야한다.
if(current_Info.hores>0){
//말로 이동하는 거니까 횟수를 하나 감소시킨다.
curHourse --;
//말로 이동
for(int i = 0 ; i < 8 ; i++){
int nr = curR + hr[i];
int nc = curC + hc[i];
if (!isRange(nr, nc))continue;
if(map[nr][nc]<curHourse){
if(nr==R-1 && nc ==C-1){
return nextMove;
}
map[nr][nc] = curHourse;
queue.add(new Info(nr, nc, curHourse, nextMove));
}
}
}
}
//정답 도착지에 도착할 수 없는 경우라면 -1을 리턴해야한다.
return -1;
}
[전체 코드]
import java.util.ArrayDeque;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
static class Info {
int r;
int c;
int hores; //말로 이동할 수 있는 남은 기회
int move ; //움직인 횟수
public Info(int r, int c, int hores,int move) {
this.r=r;
this.c=c;
this.hores=hores;
this.move=move;
}
}
static int [][]map;
static int K;
static int R,C;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
K = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
C =Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
map = new int[R][C];
for(int i = 0 ; i <R ;i++){
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j<C;j++){
int n = Integer.parseInt(st.nextToken());
if(n==1){ //장애물일때
map[i][j] = Integer.MAX_VALUE;
}else {
//평지일때 -1로 초기화. -> 그 이유는 map에 남은 말처럼 이동할 수 있는 남은 횟수를 저장할꺼기 때문 따라서 0값도 올 수 있기때문에 -1로 초기화.
map[i][j] = -1;
}
}
}
System.out.println(bfs(new Info(0,0,K,0)));
}
private static int bfs (Info info) {
int [] dr = {0,0,1,-1};
int [] dc = {1,-1,0,0};
int [] hr = {-1, 1, -1, 1, -2, 2, -2, 2};
int [] hc = {-2, -2, 2, 2, -1, -1, 1, 1};
Queue<Info> queue = new ArrayDeque<>();
queue.add(info);
if (R == 1 && C== 1) return 0;
while (!queue.isEmpty()) {
Info current_Info = queue.poll();
int curR = current_Info.r;
int curC = current_Info.c;
int nextMove = current_Info.move +1;
int curHourse = current_Info.hores;
//상 하 좌 우 인접이동
for(int i = 0 ; i <4 ; i++){
int nr = curR + dr[i];
int nc = curC + dc[i];
//2차원 배열의 범위를 넘어가는 경우는 넘겨준다.
if (!isRange(nr, nc) )continue;
//이 조건을 한 이유는
// 예를 들어 어떠한 좌표에 원숭이가 도착했다고 치자. (3,2)좌표라고 해보겠다.
// 이 좌표에 처음 도착했을때 move값이 그 칸에 갈 수 있는 가장 최소의 값일 것이다.
// 이때 남은 말의 회수가 1이였다고 치고 map[3][2]=1을 저장하였다.
//또 어떠한 경로로 인해 map[3][2]에 올 수 있는 경우가 있다. 이때 move값은 처음도착했을때의 값보다 클 것이다.
//하지만 map[nr][nc]=1이였을 때 , 이 걸로 도착지(정답)에 도착한다는 보장이 없다.
//따라서 map[nr][nc] <curHourse 말로이동할 수 있는더 큰 경우가 존재한다면 그 경우에도 탐색을 해 주어야하기때문에 이 조건문을 썼다.
if(map[nr][nc]<curHourse){
//도착지에 도착했다면 이동 횟수를 리턴한다.
//큐에서 꺼낸 Info의 move값은 최소값으로 수 밖에 없다.
//큐에 move가 1일때,2일때,3일때 순으로 차례로 저장되기 때문이다.
if(nr==R-1 && nc ==C-1){
return nextMove;
}
//map에 남은 말처럼 이동 할 수 있는 횟수를 저장한다.
map[nr][nc] = curHourse;
queue.add(new Info(nr, nc, curHourse, nextMove));
}
}
//말처럼 이동 하는 경우
// 남은 횟수가 0보다 커야한다.
if(current_Info.hores>0){
//말로 이동하는 거니까 횟수를 하나 감소시킨다.
curHourse --;
//말로 이동
for(int i = 0 ; i < 8 ; i++){
int nr = curR + hr[i];
int nc = curC + hc[i];
if (!isRange(nr, nc))continue;
if(map[nr][nc]<curHourse){
if(nr==R-1 && nc ==C-1){
return nextMove;
}
map[nr][nc] = curHourse;
queue.add(new Info(nr, nc, curHourse, nextMove));
}
}
}
}
return -1;
}
private static boolean isRange (int r,int c){
return r>=0 && r<R && c>=0 && c<C;
}
}[결과]
'Baekjoon' 카테고리의 다른 글
| [JAVA] 백준 20160번 : 야쿠르트 아줌마 야쿠르트 주세요 (1) | 2022.12.25 |
|---|---|
| [Java] 백준 1238 : 파티 (0) | 2022.12.22 |
| [Java] 백준 1034 : 램프 (0) | 2022.10.03 |
| [Java] 백준 1043 : 거짓말 (0) | 2022.10.01 |
| [Java] 백준 10159 : 저울 (0) | 2022.04.14 |
