[백준] S2 3987 보이저 1호 (java)

https://www.acmicpc.net/problem/3987

3987번: 보이저 1호

 

풀이

 

0) 방향이 존재하므로 3차원 방문체크배열을 만든다. isVisited[][][4]

1) 어떤 방향에서 어떤 행성(/ or \)을 만날때 방향이 어디로 바뀌는지 알면 된다.

2) URDL 을 0123 이라고 할 경우 

2-1) / 행성을 지날경우 1032 로 바뀐다. => dir = dir^1

2-2) \행성을 지날경우 3210 으로 바뀐다. => dir = 3-dir

3) 모든 방향으로 시그널을 보내서 

3-1) 밖으로 나가거나 (!isIn(r,c)) 블랙홀에 막힐때까지 (map[][] = 'C') 탐색을 한다. 탐색한 곳은 방문체크를 한다.

3-2) 만약 방문한 곳을 또 방문하게 된다면 무한루프를 돈다는 의미이다.

4) 결과 출력

 

주의사항

 

1) "만약, 방향이 여러 가지가 존재한다면, U, R, D, L의 순서 중 앞서는 것을 출력한다." => 반드시 방향은 위, 오른쪽, 아래, 왼쪽 순서여야 함.

2) Voyager 를 Voyger로 써서 왜 안되지 하고 30분 날렸다. 🧡✨ㅅㅂ💎🎇

 

package com.baekJoon;

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

public class BJ_S2_3987_보이저1호 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,M, PR,PC, max = Integer.MIN_VALUE;
	static char map[][], answer;
	static boolean isVisited[][][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new char[502][502];
		isVisited = new boolean[502][502][4];
		for(int r=0; r<N; r++) {
			String line = input.readLine();
			for(int c=0; c<M; c++) {
				map[r][c] = line.charAt(c);
			}	
		}
		tokens = new StringTokenizer(input.readLine());
		PR = Integer.parseInt(tokens.nextToken())-1;
		PC = Integer.parseInt(tokens.nextToken())-1;
		
		outer : for(int dir=0; dir<4; dir++) {
			int cnt = 0;
			isVisited = new boolean[N][M][4];
			int nr = PR;
			int nc = PC;
			int curDir = dir;
			while(true) {
				cnt++;
				if(!isVisited[nr][nc][curDir]) {
					isVisited[nr][nc][curDir] = true;
				}else {
					answer = d[dir];
					max = Integer.MAX_VALUE;
					break outer;
				}
				nr += dr[curDir];
				nc += dc[curDir];
				if(!isIn(nr, nc) || map[nr][nc] == 'C') {
					if(max < cnt) {
						answer = d[dir]; 
						max = cnt;
					}
					break;
				}
				if(map[nr][nc] == '/') {
					curDir = curDir ^ 1;
				}else if(map[nr][nc] == '\\') {
					curDir = 3-curDir;
				}
			}
		}
		System.out.println(answer);
		if(max == Integer.MAX_VALUE) {
			System.out.println("Voyger");
		}else {
			System.out.println(max);
		}
	}
	static char d[] = {'U', 'R', 'D', 'L'};
	static int dr[] = {-1,0,1,0}; // 상, 우, 하, 좌
	static int dc[] = {0,1,0,-1};
	static boolean isIn(int r, int c) {
		return (r>=0 && r<N && c>=0 && c<M);
	}
	
	static String src =
			"5 7\r\n"
			+ "/.....\\\r\n"
			+ "../..\\.\r\n"
			+ "\\...../\r\n"
			+ "/.....\\\r\n"
			+ "\\.\\.../\r\n"
			+ "3 3";
}

 

후기

 

 이 문제에서 여태까지 해당 유형에서 내 접근법이 많이 아쉬웠다는 것을 알게되었다. 여태까지 방향을 바꿀때는 switch-case 문으로 위, 아래, 오른쪽, 왼쪽의 경우를 일일이 따졌는데 문제에 따라서 규칙을 발견할 수 있다는 것을 알게되었다. 또한 방향을 dir[] 배열에 정답 출력용 문자를 저장하는 것도 신박했고, 한칸씩 이동하는 것을 항상 ++ 이나 -- 로 풀어서 코드가 길어졌는데, dr[], dc[]로 하는 것도 배울점 이었다.