알고리즘매일매일

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo

빈칸인 모든 칸으로부터  상하좌우 네 방향으로 모두 출발해보고 점수를 구하면된다. 그렇게 나온 점수 중 최댓값이 정답이다.

게임을 시작했으면 이동한 칸에 따라 처리해주면 된다.

1. 범위를 넘어간 경우(벽에 부딪힌 경우)에는 점수를 얻고 방향 전환 후에 바로 다음 칸으로 이동한다.

2. 출발 위치로 돌아오면 게임 종료

3. 블랙홀(-1)이면 게임 종료

4. 빈칸인 경우 계속 방향대로 이동

5. 블록인 경우(1~5)에는 각 블록의 방향에 맞게 방향을 전환해주고 점수를 얻는다.

6. 웜홀인 경우 같은 번호의 반대편 웜홀로 이동

웜홀의 경우에는 다음과 같이 x,y좌표를 가지는 벡터를 배열에 저장해서 구현하였다.

예를 들어 5번 웜홀의 좌표는 wormhole[0][0]과 wormhole[0][1]에 각각 들어있고, 6번 웜홀은 wormhole[1][0]과 wormhole[1][1]에 각각 들어있다. 게임판 배열에 들어있는 값에서 5를 빼준 값을 wormhole 배열의 인덱스로 사용하면 된다. (ex. 6번 웜홀의 인덱스는 1번)

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo

이 문제에서 어려웠던 부분은 웜홀 부분인 것 같다.

나는 웜홀의 좌표를 저장할 Wormhole클래스를 만들고 배열에 넣어주었다.

2차원 배열에 넣어서 각 6~10 번호마다 두 개씩 이므로 배열의 크기는 5X2가 된다. (웜홀은 쌍으로 존재하므로)

웜홀이 더 적게 존재할수도 있지만 최대 5개밖에 안되므로 그냥 한 번에 배열로 만들어줬다.

웜홀 배열의 각 좌표의 초기값을 -1로 설정해주고 이 점을 이용해서 두 개의 쌍을 차례대로 넣어준다.

예전에는 클래스를 만드는 대신에 3차원 int배열로 만들어 줬었다.(5X2X2 크기)

핀볼의 이동

1. 출발 위치와 진행 방향을 임의로 설정하여 점수의 최댓값을 구하는 문제이므로 모든 빈 칸(값이 0인 칸)에서 각 네 방향으로 출발해서 모든 경우의 점수를 구한다.
2. 각 이동에서는 블록의 모양에 따라서 적절히 방향을 잘 바꾸어 주며 이동시키고 블록이나 벽에 부딪힐 경우(범위 벗어나는 경우) 점수를 증가시킨다.
3. 웜홀을 만난 경우에는 방향을 유지한 채 반대편 웜홀로 이동한다.
4. 조건에 따라 핀볼이 출발 위치로 돌아오거나 블랙홀에 빠지는 경우가 될때까지 while문을 이용해 핀볼의 이동을 반복한다.
5. 핀볼의 이동이 끝나면 그때의 점수를 현재 최대 점수와 비교해준다.

import java.io.*;
import java.util.*;

public class Solution {
	
	static class Wormhole {
		int x;
		int y;
		Wormhole(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int N, max;
	static int[][] map;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static Wormhole[][] holeArr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			
			StringTokenizer st;
			map = new int[N][N];
			holeArr = new Wormhole[5][2];
			
            
            //웜홀의 위치 초기화 
			for(int i=0; i<5; i++) {
				for(int j=0; j<2; j++) {
					holeArr[i][j] = new Wormhole(-1,-1);
				}
			}
			
			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());
                    
                    //웜홀인 경우
                    //6번 웜홀부터 시작하므로 6번 웜홀이 0번째 index가 된다. 7번이 1, 8번이 2,,, 
					if(map[i][j] >= 6) {
                    
                    	//웜홀 첫 번째
						if(holeArr[map[i][j]-6][0].x == -1 && holeArr[map[i][j]-6][0].y == -1) {
							holeArr[map[i][j]-6][0].x = i;
							holeArr[map[i][j]-6][0].y = j;
						} else { //이미 첫 번째 웜홀의 위치가 저장되어 있는 경우 반대편 웜홀 저장
							holeArr[map[i][j]-6][1].x = i;
							holeArr[map[i][j]-6][1].y = j;
						}
					}
                    
				}
			}			
			
			max = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
                	
                    //빈칸이 아닌경우(블록이나 웜홀, 블랙홀인 경우)
					if(map[i][j] != 0) continue;
					
                    //상하좌우 각 방향으로 출발
					for(int k=0; k<4; k++) {
						move(i,j,k);
					}		
					
				}
			}
			
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void move(int x, int y, int dir) {
		
		int nx = x;
		int ny = y;
		int point = 0;
		
		while(true) {
        
        	//이동
			nx += dx[dir];
			ny += dy[dir];
			
            
            //벽에 부딪힌 경우 점수 증가하고 방향 전환
			if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
				point++;
				if(dir == 0 || dir == 2) {
					dir++;
				} else {
					dir--;
				}

				continue;
			}
			
            
            //블랙홀에 빠짐
			if(map[nx][ny] == -1) {
				break;
			}
			
            
            //출발위치로 돌아옴
			if(x == nx && y == ny) {
				break;
			}
			
            
            
			if(map[nx][ny] == 0) {
            	//빈칸이므로 방향유지한채 바로 이동
				continue;
			} else if(map[nx][ny] == 1) { //각 블록의 종류에따라서 방향을 변환해주고 점수도 증가
				if(dir == 0) {
					dir = 2;
				} else if(dir == 1) {
					dir = 0;
				} else if(dir == 2) {
					dir = 3;
				} else {
					dir = 1;
				}
				
				point++;
				
			} else if(map[nx][ny] == 2) {
				if(dir == 0) {
					dir = 1;
				} else if(dir == 1) {
					dir = 2;
				} else if(dir == 2) {
					dir = 3;
				} else {
					dir = 0;
				}
				
				point++;
				
			} else if(map[nx][ny] == 3) {
				if(dir == 0) {
					dir = 1;
				} else if(dir == 1) {
					dir = 3;
				} else if(dir == 2) {
					dir = 0;
				} else {
					dir = 2;
				}
				
				point++;
				
			} else if(map[nx][ny] == 4) {
				if(dir == 0) {
					dir = 3;
				} else if(dir == 1) {
					dir = 0;
				} else if(dir == 2) {
					dir = 1;
				} else {
					dir = 2;
				}
				
				point++;
				
			} else if(map[nx][ny] == 5) {
				if(dir == 0 || dir == 2) {
					dir++;
				} else {
					dir--;
				}
				
				point++;
				
			} else { //웜홀인 경우 반대편 웜홀로 이동
				int holenum = map[nx][ny]-6;
				if(nx == holeArr[holenum][0].x && ny == holeArr[holenum][0].y) {
					nx = holeArr[holenum][1].x;
					ny = holeArr[holenum][1].y;
				} else {
					nx = holeArr[holenum][0].x;
					ny = holeArr[holenum][0].y;
				}
			}
		}
		
        
        //이동이 끝난 후에 점수 비교
		if(max < point) {
			max = point;
		}
	}

}