개요

문제링크

발상의 전환을 하면 단순하게 풀리는 문제

생각을 거꾸로 해보자!

문제분석

2로 적혀있는 골인지점으로 도달할 수 있는 첫 지점을 알아내는 문제이다.

이 문제는 매우매우 단순하다! 사다리 타기를 할때, 우리는 내가 어디에서 시작할지 선택한다. 선택하고 나면 내가 도착할 지점이 나는 모르지만 정해진다.

이러한 점을 생각해보면 이 문제는 아주 쉽게 풀린다.

이미 문제에서는 출발지점을 주고있다. 우리는 그냥 그대로 따라가면 정답이 나오는 것이다.

우리는 2인 지점을 저장해놓고, 그대로 사다리를 따라갈것이다. 그리고 마지막에 도착하는 지점 (x좌표가 0인 지점)의 좌표만 알려주면 된다.

이 문제의 경우 visited 배열을 사용하여 내가 되돌아 왔던 길을 다시 돌아가지 않도록만 신경써주면 아주 쉽게 풀리는 문제이다.

더불어 내가 가는 방향은 항상 정해져있다.

왼쪽 혹은 오른쪽에 갈 수 있는 길이 있다면. 그곳으로 직진하면 되고 만약 왼쪽 오른쪽으로 둘다 못간다면 위로가면 된다.

즉, 세가지의 경우의 수만 체크하면 된다.

문제풀이

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

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * @see
 * @since 11/27/23
 **/
public class Solution {
	static int T = 10;
	static int N = 100;
	static int[][] map;
	static int[] start;
	static int[] dx = {-1,0,0}; // 상 좌 우
	static int[] dy = {0,-1,1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		for(int t=1;t<T+1;t++){
			br.readLine(); // 테스트 케이스 번호
			map = new int[N][N];
			start = new int[2];


			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] == 2) start = new int[]{i,j};
				}
			}
			//거꾸로 올라갑니당
			int x = start[0];
			int y = start[1];
			int dir = 0; // default = up

			boolean[][] visited = new boolean[N][N];
			visited[x][y] = true;

			while(true){
				for(int i=0;i<3;i++){
					int nx = x + dx[i];
					int ny = y + dy[i];
					if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
					if(map[nx][ny] == 1 && !visited[nx][ny]) dir = i;
				}
				//왼쪽 혹은 오른쪽에 길이 있다면 그곳을 먼저간다
				//만약 없다면 올라간다
				if(x + dx[dir] == 0) break;
				x += dx[dir];
				y += dy[dir];
				visited[x][y] = true;
			}

			System.out.printf("#%d %d\n",t,y);

		}
	}
}