문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo&categoryId=AWXRF8s6ezEDFAUo&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98+sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

코드 (Java)

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

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
class Solution
{
	private static final int EMPTY = 0, BLACK_HOLE = -1;
	private static int[][] blockDir = {{}, 
										{2, 0, 3, 1},
										{2, 3, 1, 0},
										{1, 3, 0, 2},
										{3, 2, 0, 1},
										{2, 3, 0, 1}};
	private static int[][] map = new int[100][100]; //map we're examining
	private static int[][][] wormHoles = new int[5][2][2]; //wormhole start/end position
	private static int dirMove[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
	
	/* for dir variable
	 * 0 : East
	 * 1 : South
	 * 2 : West
	 * 3 : North
	 */
	
	private static int N;
	
	public static void main(String args[]) throws Exception
	{
		/*
		   아래의 메소드 호출은 앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
		   여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
		   이 코드를 프로그램의 처음 부분에 추가하면 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
		   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 메소드를 사용하셔도 좋습니다.
		   단, 채점을 위해 코드를 제출하실 때에는 반드시 이 메소드를 지우거나 주석 처리 하셔야 합니다.
		 */
		System.setIn(new FileInputStream("res/input.txt"));
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T=Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			int maxScore = 0;
			
			//obtain map input and initialize all metadatas
			N = Integer.parseInt(br.readLine().trim());
			//visited = new boolean[N][N][4];
			
			for (int idx = 0; idx < 5; ++idx) {
				wormHoles[idx][0][0] = -1;
			}
			
			for (int row = 0; row < N; ++row) {
				StringTokenizer input = new StringTokenizer(br.readLine());
				for (int col = 0; col < N; ++col) {
					map[row][col] = Integer.parseInt(input.nextToken());
//					System.out.printf("%d ", map[row][col]);
					if (map[row][col] > 5) { //it's a wormhole.
						int idx = wormholeIdx(map[row][col]);
						if (wormHoles[idx][0][0] == -1) {
							wormHoles[idx][0][0] = row;
							wormHoles[idx][0][1] = col;
						} else {
							wormHoles[idx][1][0] = row;
							wormHoles[idx][1][1] = col;
						}
					}
				}
//				System.out.printf("\n");
			}
			
			
			//we calculate the score.
			for (int row = 0; row < N; ++row) {
				for (int col = 0; col < N; ++col) {
					if (map[row][col] != 0) continue;
					for (int dir = 0; dir < 4; ++dir) {
						maxScore = Math.max(maxScore,  DFS(row, col, dir));
					}
				}
			}
			
			bw.write("#" + test_case + " " + maxScore + '\n');
			bw.flush();
		}
		
		bw.close();
	}
	
	private static int wormholeIdx(int n)
	{
		return n - 6;
	}
	
	//finding score of current position and dir, with saved results...
	private static int DFS(int startRow, int startCol, int dir) {
		
		int score = 0;
		
		int curRow = startRow;
		int curCol = startCol;
		int curDir = dir;
		int metBlockCnt = 0;
//		int iter = 0; //debugging
		
		while (true) {
//				System.out.printf("iter : %d, row : %d, col : %d, dir : %d\n", iter, curRow, curCol, curDir);
//				++iter;
				int newRow = curRow + dirMove[curDir][0];
				int newCol = curCol + dirMove[curDir][1];
				if (!(newRow >= 0 && newRow < N && newCol >= 0 && newCol < N)) {
					//we met the wall. Impossible to move.
					//we reflect. score is added.
					score = metBlockCnt*2 + 1;
					break;
				}
				else if (map[newRow][newCol] == BLACK_HOLE) {
					//we met the black hole. finished.
					score = metBlockCnt;
					break;
				}
				else if (map[newRow][newCol] >= 6) {
					//we met the wormhole.
					int idx = wormholeIdx(map[newRow][newCol]);
					int pos1r = wormHoles[idx][0][0], pos1c = wormHoles[idx][0][1];
					if (pos1r == newRow && pos1c == newCol) {
						curRow = wormHoles[idx][1][0];
						curCol = wormHoles[idx][1][1];
					} else {
						curRow = pos1r; curCol = pos1c;
					}
				}
				else if (map[newRow][newCol] != EMPTY) {
					//we met the block. update position and continue moving.
					//metBlockCnt also increased. we may need to go into record mode.
					int newDir = blockDir[map[newRow][newCol]][curDir];
					if (newDir == (curDir + 2) % 4) {
						//reflected. go into record mode.
						score = metBlockCnt*2 + 1;
						break;
					} else {
						++metBlockCnt;
						curRow = newRow;
						curCol = newCol;
						curDir = newDir;
					}
				}
				else if (newRow == startRow && newCol == startCol) {
					//returned to original position somehow by teleporting.
					score = metBlockCnt;
					break;
				}
				else {
					//we just update as usual.
					curRow = newRow;
					curCol = newCol;
				}
			
		}
		
//		System.out.printf("after %d iter for startRow %d and startCol %d and startDir %d, score %d achieved.\n", iter, startRow, startCol, dir, score);
		
		return score;
	}
}

풀이

• 시뮬레이션/구현 문제다. DFS랑 유사하다.

• 100x100이 최대이며 시작점에 다시 도달하거나 블랙홀을 만나면 종료되는 것을 고려시 대략 100 x 100 x 2 x 4 x 100 x 100 = 8 * 10^8이 최악의 테스트케이스 경우이지만 실제로 이 경우에 도달하는 경우가 별로 없어서 생각보다 널널하다...고 볼 수 있지만 유의해야할게 몇가지 있다.

  • 반사시 돌아오는 것을 굳이 계산할 필요가 없다는 점을 활용하자.
  • 반사 '없이' 시작점에 돌아올 수 있다는 점을 유의하자. 이에 따라 계산해야하는 점수가 달라진다.
  • 필자는 더 연산횟수가 줄어들 수 있도록 위치/방향에 따른 점수를 기록하려고 했으나 이러면 semantic 면에서 문제가 생긴다. 그래서 이 부분으로 최적화하려고 시도하진 말자.
  • BufferedReader의 경우 trim()을 사용하는 것을 습관화할 필요가 있다. (삼성 한정) N read시에 공백이 있어서 br.readLine()을 그냥 parse하면 runtime error이 발생한다.
  • 구상을 확실히하고 코딩을 하자. 애매하게 하다가 반례가 여러개 나와서 코딩하는데 시간이 매우 오래 걸렸다.