[JAVA] 백준 8972 : 미친 아두이노

문제

8972번: 미친 아두이노

 

해결 방법

다 풀고 나서 보니 BFS 방법을 이용해서 푸신 분들도 있었다.

그 분들에 비하면 내 코드가 속도가 느리긴 하지만, 이런 코드도 있다 정도로 봐주면 좋겠다.

 

문제의 1~5번을 순서대로 구현했고,

방향은 dx, dy 배열을 통해 입력해두었다.

입력의 젤 마지막에 종수가 움직이는 방향이 주어지는데, 주어질 때마다 moveI 함수를 실행시켜 전체 맵을 변경시켜주었다.

 

moveI 함수는 처음에 입력받은 값에 따라 종수 아두이노를 움직이고,

종수 아두이노는 맵을 벗어나는 값은 주어지지 않기 때문에 범위를 체크할 필요는 없다.

 

종수 아두이노가 움직인 곳에 미친 아두이노가 있다면 false를 반환해서 몇 번째 시도에서 실패했는지 출력이 되며,

없다면 crazy 리스트에 담아둔 미친 아두이노들을 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때,

|r1-r2| + |s1-s2| 가 가장 작아지는 방향으로 이동시켜 준다.

 

이 때 visit 배열을 사용해서 미친 아두이노들이 겹쳐지는 것을 체크해두고 visit 배열의 값이 2보다 크면 겹쳐진 것이기 때문에 removeR 리스트에 담아둔다.

 

그 다음에 crazy 리스트와 종수의 아두이노 위치를 비교해서 같다면 미친 아두이노가 종수의 아두이노의 칸으로 이동한 것이므로 false를 반환해 종료시키고, 아니라면 미친 아두이노가 겹쳐있는 곳을 체크해서 crazy 리스트에서 제거해준다.

 

위와 같이 1 ~ 5번을 다 진행한 이후에 draw 함수를 호출해서 맵을 다시 그려주고 처음부터 반복한다.

자세한 설명은 부분마다 주석을 달아 두었다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int dx[] = {1, 1, 1, 0, 0, 0, -1, -1, -1};
	static int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
	
	static int R, C;
	static char[][] map;
	static ArrayList<Node> crazy;
	static Node arduino;
	
    public static void main(String[] args) throws IOException {
        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];
        crazy = new ArrayList<>();
        
        for (int i = 0; i < R; i++) {
        	String input = br.readLine();
        	for (int j = 0; j < C; j++) {
        		map[i][j] = input.charAt(j);
        		
        		if (map[i][j] == 'I') {
        			arduino = new Node(i, j);
        		}
        		
        		if (map[i][j] == 'R') {
        			crazy.add(new Node(i, j));
        		}
        	}
        }
        
        StringBuilder sb = new StringBuilder();
        String input = br.readLine();
        for (int i = 0; i < input.length(); i++) {
        	int move = input.charAt(i) - '0';
        	if (!moveI(move)) {
        		System.out.println("kraj " + (i + 1));
        		return;
        	}
        }
        
        for (int i = 0; i < R; i++) {
        	for (int j = 0; j < C; j++) {
        		sb.append(map[i][j]);
        	}
        	sb.append("\n");
        }
        System.out.println(sb);
    }
    
    static boolean moveI(int move) {
    	int newX = arduino.x + dx[move - 1];
    	int newY = arduino.y + dy[move - 1];
    	
    	if (map[newX][newY] == 'R') return false;
    	// 아두이노가 미친 아두이노칸으로 이동하면 바로 종료.
    	
    	if (map[newX][newY] == '.') {
    		arduino = new Node(newX, newY);
    	}
    	
    	int visit[][] = new int[R][C];
    	ArrayList<Node> removeR = new ArrayList<>();
    	// 미친 아두이노가 같은 칸에 있는지 확인하는 용도
    	
    	for (Node temp : crazy) {
    		// 8가지 중 가장 가까운 방향 찾기
    		int min = Integer.MAX_VALUE;
			int crazyX = 0;
			int crazyY = 0;
			
    		for (int i = 0; i < 9; i++) {
    			if (i == 4) continue; // 가만히 있는 상태는 넘김
    			
    			int moveX = temp.x + dx[i];
    			int moveY = temp.y + dy[i];
    			if (moveX < 0 || moveY < 0 || moveX >= R || moveY >= C) continue;
    			
    			// 종수와 가장 가까워 지는 칸이라면 값들을 다 바꿔줌
    			if (min > Math.abs(arduino.x - moveX) + Math.abs(arduino.y - moveY)) {
    				min = Math.abs(arduino.x - moveX) + Math.abs(arduino.y - moveY);
    				crazyX = moveX;
    				crazyY = moveY;
    			}
    		}

			// 리스트 내부 값도 수정
			temp.x = crazyX;
			temp.y = crazyY;
			
			visit[crazyX][crazyY] += 1;
			if (visit[crazyX][crazyY] >= 2) {
				removeR.add(new Node(crazyX, crazyY));
			}
    	}
    	
    	// 같은 칸에 미친 아두이노가 있다면 다 없애기
    	for (int i = 0; i < crazy.size(); i++) {
    		// 미친 아두이노가 종수의 아두이노와 같은 칸에 있으면 종료
    		if (crazy.get(i).x == arduino.x && crazy.get(i).y == arduino.y) return false;
    		
    		// 제거 목록과 일치한다면 제거
    		for (int j = 0; j < removeR.size(); j++) {
    			if (removeR.get(j).x == crazy.get(i).x && removeR.get(j).y == crazy.get(i).y) {
        			crazy.remove(i);
        			i--;
        			break;
        			// 제거 완료 했기 때문에 다시 앞쪽 for문에서 탐색.
    			}
    		}
    	}
    	
    	draw();
    	// 수정된 값을 바탕으로 다시 맵 그리기
    	return true;
    }
    
    static void draw() {
    	for (int i = 0; i < R; i++) {
    		Arrays.fill(map[i], '.');
    	}
    	
    	map[arduino.x][arduino.y] = 'I';
    	for (Node temp : crazy) {
    		map[temp.x][temp.y] = 'R';
    	}
    }
}

class Node {
	int x;
	int y;
	
	Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}