-
문제
요즘 종수는 아두이노를 이용해 "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는 종수가 게임이 끝나기 전까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.
풀이
해당 문제는 시뮬레이션 문제로 문제에서 주어진 대로 구현을 진행하면 해결 가능한 문제다. 로직은 아래와 같은 방식으로 구현하였다.
다만 R을 이동시킬 때 R 간에 충돌을 체크하기 위해 새로운 배열에 이동시켜줌으로써 이동 전의 R과 이동 후의 R 충돌을 방지할 수 있었다.
1. 입력 처리를 한다 이때 I는 좌표값을 저장하고, R은 큐에 좌표값을 담아준다.
2. 무한 반복을 돌면서 아래와 같은 로직을 수행한다.
3. I를 이동시킨다.
3-1. 이동 방향에 대해 좌표값을 경신해주고 이동하려는 곳이 R인 경우 종료한다.
4. R을 이동시킨다.
4-1. 큐에 크기만큼 반복하며 큐에서 빼낸 좌표와 I 좌표를 비교한다.
4-2. 비교를 통해 좌표 선상의 위치를 체크하여 연산을 한다. (같은 가로 선상, 같은 세로 선상, 대각선 이동)
4-3. 이동하려는 곳이 I좌표와 같다면 종료한다.
4-4. 큐에 이동하려는 좌표를 담는다.
5. R을 모두 이동시키면 map를 갱신한다.
5-1. 새로운 배열을 하나 생성한다 (R끼리 만나는 부분을 체크하기 위해, 기존 R과 충돌을 방지하기 위해)
5-2. 큐가 빌 때까지 모두 빼내어 새로운 배열을 갱신한다 (이때 이미 R인 경우 X로 변경시킴)
5-3. 갱신이 완료되면 배열을 탐색하면서 R인 부분은 큐에 담고 이외 부분은.으로 초기화한다.
5-4. 새로운 배열 값을 map로 복사한다.
6. 카운트를 1 증가시키고 이동방향을 담은 배열의 크기와 비교한다.
6-1. 사이즈가 같으면 map 배열을 출력하고 종료한다.
6-2. 사이즈가 다르면 위의 동작을 반복한다.
코드
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int R, C, ay, ax, cnt, dy[] = {0,1,1,1,0,0,0,-1,-1,-1}, dx[] = {0,-1,0,1,-1,0,1,-1,0,1}; // 1~9지니깐 첫번째에 더미 추가 static char map[][], index[]; static Queue<Node> q = new LinkedList<>(); public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); R = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken()); map = new char[R][C]; for (int i = 0; i < R; i++) { // 입력처리 map[i] = br.readLine().toCharArray(); for (int j = 0; j < C; j++) { if(map[i][j] == 'I') { map[i][j] ='.'; ay = i; ax = j; }else if(map[i][j] == 'R') { q.add(new Node(i,j)); } } } index = br.readLine().toCharArray(); // 이동해야하는 방향 저장 while(true) { if(move_Arduino()) { // 아두이노를 이동시킨다. System.out.println("kraj "+(cnt+1)); break; } if(move_Crazy_Arduino()) { // 미친 아두이노를 이동시킨다. System.out.println("kraj "+(cnt+1)); break; } map_Check(); if(++cnt == index.length) { // 모두 이동했다면 출력하고 종료 print(); break; } } } private static void print() { map[ay][ax] = 'I'; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { System.out.print(map[i][j]); } System.out.println(); } } private static void map_Check() { // 이동시킨 좌표를 가지고 map를 갱신함 이때 새로운 배열을 만들어서 큐에있는 값을 갱신해줌 R에대해서 기존값과 충돌 방지 char copy[][] = new char[R][C]; while(!q.isEmpty()) { Node n = q.poll(); if(copy[n.y][n.x] != 'R' && copy[n.y][n.x] != 'X') // R의 단순 이동 copy[n.y][n.x] = 'R'; else // R이 있는곳으로 이동 copy[n.y][n.x] = 'X'; } for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if(copy[i][j] == 'R') // R은 큐에 다시 담고 q.add(new Node(i,j)); else // null 과 X 는 .으로 갱신 copy[i][j] = '.'; map[i][j] = copy[i][j]; // 배열 복사 } } } private static boolean move_Crazy_Arduino() { // 큐의 사이즈만큼 돌면서 이동시키고 다시 큐에담음 int size = q.size(); for(int i= 0;i<size;i++) { Node n = q.poll(); if(n.y == ay) { // 같은 가로 선상 if(n.x > ax) n.x--; else n.x++; }else if(n.x == ax) { // 같은 세로 선상 if(n.y > ay) n.y--; else n.y++; }else { // 대각선 이동 // 여기는 사분면으로 총 4가지 조건으로 체크 if (ay > n.y && ax > n.x) { // 오른쪽 상단으로 이동 n.y++; n.x++; }else if (ay < n.y && ax > n.x) { // 오른쪽 하단으로 이동 n.y--; n.x++; }else if (ay < n.y && ax < n.x) { // 왼쪽 상단으로 이동 n.y--; n.x--; }else if (ay > n.y && ax < n.x) { // 왼쪽 하단으로 이동 n.y++; n.x--; } } if(n.y == ay && n.x == ax) // 이동한곳이 I 좌표라면 종료 return true; q.add(new Node(n.y,n.x)); } return false; } private static boolean move_Arduino() { // 이동방향 값을 더해주고 R인 경우 실패 ay += dy[index[cnt] - '0']; ax += dx[index[cnt] - '0']; if(map[ay][ax] == 'R') { return true; } return false; } static class Node{ int y, x; Node(int y, int x){ this.y = y; this.x = x; } } }
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 21736 헌내기는 친구가 필요해 JAVA (0) 2022.06.14 Baekjoon 4577 소코반 JAVA (0) 2022.06.13 Baekjoon 13913 숨바꼭질 4 JAVA (0) 2022.06.06 Baekjoon 17086 아기 상어 2 JAVA (0) 2022.06.05 Baekjoon 1302 베스트셀러 JAVA (0) 2022.06.01 댓글