5650. [모의 SW 역량테스트] 핀볼 게임

주어진 게임판의 모든 빈 공간에서 핀볼을 동서남북 방향으로 모두 출발시켜 보는 완전탐색 시뮬레이션 문제입니다. 저는 Ball 클래스를 만들어서 빈공간의 모든 위치 x, y와 동서남북 방향을 뜻하는 d에 0,1,2,3 을 넣어서 ArrayList에 담고 모든 빈 공간에서 핀볼게임을 동서남북방향으로 시작했습니다.

그리고 웜홀을 처리하는 것이 문제였는데 웜홀 또한 Hole이라는 클래스를 만들어서 ArrayList에 모든 웜홀의 위치 x, y를 저장했습니다. 그래서 핀볼이 움직이면서 웜홀을 만나게 되면 모든 웜홀이 담긴 ArrayList를 전체 탐색하면서 자기 자신의 다른 짝 웜홀을 찾아서 그 위치로 이동시키는 방법으로 처리했습니다. 이 부분은 생각해보면 웜홀은 한 쌍으로 이루어져 있기 때문에 더 효율적으로 처리할 수 있을것 같은데 문제에서 웜홀은 최대 5쌍이 주어지기 때문에 메모리에 영향이 크지 않다고 생각해서 단순하게 구현해봤습니다. 나중에 문제를 다시 풀게 된다면 더 효율적으로 구현하여 시간을 줄여보도록 해야겠습니다.

[ 문제 풀이 ]

1. 빈 공간(입력 받은 게임판에서 값이 0인 부분)의 x, y좌표와 핀볼을 출발방향을 나타내는 0,1,2,3 (동서남북) 을 ArrayList list에 저장합니다.

2. 웜홀(입력 받은 게임판에서 값이 6 이상 10이하인 부분)의 x, y좌표를 ArrayList holes에 저장합니다.

3. 모든 정보를 입력받고 start() 함수로 게임을 시작합니다. 게임을 할 수 있는 모든 핀볼의 위치를 담은 list를 모두 돌면서 주어진방향으로 게임을 시작합니다.

4. 게임 진행중에 핀볼이 시작위치, 블랙홀을 만나면 게임을 종료합니다.

5. 블럭이나 벽을 만나면 점수를 1증가시키는데, 벽을 만나면 게임판을 벗어난 것이기 때문에 방향을 반대방향으로 바꿔줍니다. 그리고 블럭을 만나게 되면 changeDirection() 으로 방향을 바꿔줍니다. changeDirection() 은 단순이 방향을 반대방향으로 바꿔주는 것이 아닌 블록마다 들어온 방향에 따라 바뀌기 때문에 따로 구현했습니다.

6. 웜홀을 만나게되면 모든 웜홀이 담긴 holes 를 탐색하면서 짝 웜홀을 찾아서 그 위치로 이동시킵니다.

---

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

public class Solution {
	
	static class Ball {
		int x;
		int y;
		int d;
		
		Ball(int x, int y, int d){
			this.x=x;
			this.y=y;
			this.d=d;
		}
	}
	
	static class Hole {
		int x;
		int y;
		Hole(int x, int y){
			this.x=x;
			this.y=y;
		}
	}
	
	static int N, answer;
	static int[][] map, dir = {{0,1},{0,-1},{1,0},{-1,0}};
	static ArrayList<Ball> list;
	static ArrayList<Hole> holes;
	static int[] change = {1,0,3,2};
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine()); 
		
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			list = new ArrayList();
			answer = Integer.MIN_VALUE;
			holes = new ArrayList();
			// 맵 입력
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(map[i][j] == 0) {
						for(int d=0; d<=3; d++) list.add(new Ball(i, j, d));
					}
					if(map[i][j]>=6 && map[i][j]<=10) {
						holes.add(new Hole(i, j));
					}
				}
			}
			
			start();
			
			
			System.out.println("#" + tc + " " + answer);
		}
	}
	
	public static void start() {
		int score;
		
		for(int i=0; i<list.size(); i++) {
			
			Ball ball = list.get(i);
			score = 0;
			
			// d:0123 -> 동서남북
			int d = ball.d;
			int x = ball.x;
			int y = ball.y;
			int nx = x;
			int ny = y;
			
			while(true) {
				nx += dir[d][0];
				ny += dir[d][1];
				
				// 블럭이나 벽을 만났을 때
				if(!isInside(nx, ny) || (map[nx][ny] >= 1 && map[nx][ny] <= 5)) {
					score++;
					if(!isInside(nx, ny)) d = change[d];
					else d = changeDirection(d, map[nx][ny]);
					continue;
				}
				// 웜홀을 만났을 때
				if(map[nx][ny] >= 6 && map[nx][ny] <= 10) {
					for(int k=0; k<holes.size(); k++) {
						Hole h = holes.get(k);
						if(map[h.x][h.y] == map[nx][ny]) {
							if(nx == h.x && ny == h.y) continue;
							else {
								nx = h.x;
								ny = h.y;
								break;
							}
						}
					}
				}
				
				// 종료조건
				if((nx == x && ny == y) || map[nx][ny] == -1) break;
				
			}
			
			answer = Math.max(answer, score);
		}
	}
	
	public static int changeDirection(int cur, int block) {
		// d:0123 동서남북
		int d = -1;
		if(block == 1) {
			if(cur == 0) d=1;
			else if(cur == 1) d=3;
			else if(cur == 2) d=0;
			else if(cur == 3) d=2;
		} else if(block == 2) {
			if(cur == 0) d=1;
			else if(cur == 1) d=2;
			else if(cur == 2) d=3;
			else if(cur == 3) d=0;
		} else if(block == 3) {
			if(cur == 0) d=2;
			else if(cur == 1) d=0;
			else if(cur == 2) d=3;
			else if(cur == 3) d=1;
		} else if(block == 4) {
			if(cur == 0) d=3;
			else if(cur == 1) d=0;
			else if(cur == 2) d=1;
			else if(cur == 3) d=2;
		} else if(block == 5) {
			if(cur == 0) d=1;
			else if(cur == 1) d=0;
			else if(cur == 2) d=3;
			else if(cur == 3) d=2;
		}
		
		return d;
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && x<N && y>=0 && y<N;
	}
}