-
[백준]8972: 미친 아두이노(java)Algorithm/백준 2022. 5. 19. 22:38728x90
https://www.acmicpc.net/problem/8972
문제
요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. 하지만, 미친 아두이노의 움직임은 예측할 수 있다.
게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다.
- 먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
- 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다.
- 미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다. 즉, 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다.
- 미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다.
- 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.
종수의 시작 위치, 미친 아두이노의 위치, 종수가 움직이려고 하는 방향이 주어진다. 입력으로 주어진 방향대로 종수가 움직였을 때, 보드의 상태를 구하는 프로그램을 작성하시오. 중간에 게임에서 지게된 경우에는 몇 번째 움직임에서 죽는지를 구한다.
입력
첫째 줄에 보드의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 100)
다음 R개 줄에는 C개의 문자가 주어지며, 보드의 상태이다. '.'는 빈 칸, 'R'은 미친 아두이노, 'I'는 종수의 위치를 나타낸다.
마지막 줄에는 길이가 100을 넘지않는 문자열이 주어지며, 종수가 움직이려고 하는 방향이다. 5는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.
보드를 벗어나는 입력은 주어지지 않는다.
출력
중간에 게임이 끝나는 경우에는 "kraj X"를 출력한다. X는 종수가 게임이 끝나기 전 까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.
예제 입력 1
4 5 I.... ..... .R.R. ..... 6
예제 출력 1
.I... .RR.. ..... .....
풀이
시뮬레이션 문제였다.
흐름은 아래와 같다.
1. 종수가 이동한다.
2. 종수가 이동한 곳에 미친 아두이노가있는가?
3. 미친 아두이노들을 이동한다.
4. 이동후의 아두이노들이 종수와 겹치는가?
를 순서대로 잘 풀이해주면 된다.
1. 종수가 이동한다.
의 로직은 매우 간단하다.
for(int i=0; i<moving.length(); i++) { cnt++; int d = moving.charAt(i)-'0'; int nx = jongsuArduino.x + dist[d][0]; int ny = jongsuArduino.y + dist[d][1]; jongsuArduino = new Point(nx, ny); if(map[nx][ny] == 'R') { return false; } moveCrazyArduino(); if(map[nx][ny] == 'R') { return false; } }
단순히 입력받은 move 순서대로 종수를 움직여준다.
종수는 전역 클래스형 변수로 선언하였다.
2. 종수가 이동한 곳에 미친 아두이노가 있는가?
있다면 우리는 즉시 종료된다.
if(map[nx][ny] == 'R') { return false; }
3. 미친 아두이노의 이동
3-1) 아두이노들 이동하기
for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { if(map[i][j] == '.') continue; map[i][j] = '.'; int min = Integer.MAX_VALUE; int nx = 0; int ny = 0; for(int d=1; d<=9; d++) { if(!isIn(i+dist[d][0], j+dist[d][1])) continue; int len = getDist(i + dist[d][0], j + dist[d][1]); if(min > len) { min = len; nx = i + dist[d][0]; ny = j + dist[d][1]; } } if(isMove[nx][ny]) { isDestroyed[nx][ny] = true; } isMove[nx][ny] = true; } }
아두이노를 이동시킨다.
아두이노는 바깥으로 나갈 수 없으므로 바깥으로 나간 경우는 continue 해준다.
아두이노는 모든 방향으로부터의 최소거리를 구한다.
public static int getDist(int x, int y) { return Math.abs(x - jongsuArduino.x) + Math.abs(y - jongsuArduino.y); }
그 최소거리로 아두이노를 이동시킨다.
isMove = true를 줌으로써 그 좌표에 이미 이동했음을 알린다.
isMove가 true인데 이동하려고 하면 isDestroyed에 true를 줌으로써 폭발해야하는 자리임을 알린다.
3-2) 겹치는 아두이노 폭발
if(isDestroyed[jongsuArduino.x][jongsuArduino.y]) { System.out.printf("kraj %d", cnt); System.exit(0); } for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { if(isDestroyed[i][j]) { map[i][j] = '.'; } else if(isMove[i][j]) map[i][j] = 'R'; } }
만약 폭발하려는 아두이노 자리에 종수가 존재한다면 시뮬레이션은 종료되야한다.
완탐을 돌며 만약 파괴가 true라면 .을 그게 아니고 move가 true라면 R을 map에 입력해준다.
전체 코드
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BJ_G4_8972_미친아두이노 { static class Point{ int x; int y; Point(int x, int y) { this.x = x; this.y = y; } } static int N, M; static char[][] map; static Point jongsuArduino; static int cnt=0; static int[][] dist = {{}, {1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 0}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}}; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); map = new char[N][M]; for(int i=0; i<N; i++) { String str = br.readLine(); for(int j=0; j<M; j++) { map[i][j] = str.charAt(j); if(map[i][j] == 'R') { } else if(map[i][j] == 'I') { map[i][j] = '.'; jongsuArduino = new Point(i, j); } } } String moving = br.readLine(); if(goSimulate(moving)) { StringBuilder ans = new StringBuilder(); map[jongsuArduino.x][jongsuArduino.y] = 'I'; for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { ans.append(map[i][j]); } if(i!=N-1) ans.append("\n"); } System.out.printf("%s", ans.toString()); } else { System.out.printf("kraj %d", cnt); } } public static boolean goSimulate(String moving) { for(int i=0; i<moving.length(); i++) { cnt++; int d = moving.charAt(i)-'0'; int nx = jongsuArduino.x + dist[d][0]; int ny = jongsuArduino.y + dist[d][1]; jongsuArduino = new Point(nx, ny); if(map[nx][ny] == 'R') { return false; } moveCrazyArduino(); if(map[nx][ny] == 'R') { return false; } } return true; } public static void moveCrazyArduino() { boolean[][] isDestroyed = new boolean[N][M]; boolean[][] isMove = new boolean[N][M]; for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { if(map[i][j] == '.') continue; map[i][j] = '.'; int min = Integer.MAX_VALUE; int nx = 0; int ny = 0; for(int d=1; d<=9; d++) { if(!isIn(i+dist[d][0], j+dist[d][1])) continue; int len = getDist(i + dist[d][0], j + dist[d][1]); if(min > len) { min = len; nx = i + dist[d][0]; ny = j + dist[d][1]; } } if(isMove[nx][ny]) { isDestroyed[nx][ny] = true; } isMove[nx][ny] = true; } } if(isDestroyed[jongsuArduino.x][jongsuArduino.y]) { System.out.printf("kraj %d", cnt); System.exit(0); } for(int i=0; i<N; i++) { for(int j=0; j<M; j++) { if(isDestroyed[i][j]) { map[i][j] = '.'; } else if(isMove[i][j]) map[i][j] = 'R'; } } } public static int getDist(int x, int y) { return Math.abs(x - jongsuArduino.x) + Math.abs(y - jongsuArduino.y); } public static boolean isIn(int x, int y) { return 0<=x && x<N && 0<=y && y<M; } }
728x90'Algorithm > 백준' 카테고리의 다른 글
[백준]1826: 연료 채우기(java) (0) 2022.05.31 [백준]2026: 소풍(java) (0) 2022.05.30 [백준]2179: 비슷한 단어(javascript) (0) 2022.05.17 [백준]2138: 전구와 스위치(java) (0) 2022.05.16 [백준]17825: 주사위 윷놀이(java) (0) 2022.05.15