[Java] SWEA1210_Ladder1

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

SW Expert Academy

[문제]

점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다.
김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다.
사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X표시에 도착하게 되는지 궁금해졌다. 이를 구해보자.

아래 <그림 1>의 예를 살펴보면, 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 개수의 막대들이 랜덤 간격으로 추가되고(이 예에서는 2개가 추가됨) 이 막대들 사이에 가로 방향의 선들이 또한 랜덤하게 연결된다.

X=0인 출발점에서 출발하는 사례에 대해서 화살표로 표시한 바와 같이, 아래 방향으로 진행하면서 좌우 방향으로 이동 가능한 통로가 나타나면 방향 전환을 하게 된다.

방향 전환 이후엔 다시 아래 방향으로만 이동하게 되며, 바닥에 도착하면 멈추게 된다.

문제의 X표시에 도착하려면 X=4인 출발점에서 출발해야 하므로 답은 4가 된다. 해당 경로는 별도로 표시하였다.

[풀이]

X에 도착하는 시작점을 알고싶은문제이므로 반대로 X에서 시작하여 위로 올라간다. 

일반적인 사다리타기의 진행 방향을 하, 우, 좌 뿐이므로 

올라가는 방향은 반대로 상, 우, 좌 뿐이다. 

플래그 변수를 두어

flag ==0 상 방향  

flag ==1 우 방향  (좌방향 변경 불가능)

flag ==2 좌 방향으로 구현해주었다. (우방향 변경 불가능)

 

package day05.hw;

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

public class SWEA1210_사다리 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("src//day05//hw//1210.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int t = 1; t <= 10; t++) {
			int tc = Integer.parseInt(br.readLine());
			int[][] arr = new int[100][100];
			int x = 99, y = 0;		//X는 무조건 맨 아래 있으므로 99 고정
			int flag = 0;			//0:상 , 1:우, 2:좌

			// input값 : 값이 2인 지점을 찾아 위치정보를 가져온다
			for (int i = 0; i < 100; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < 100; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
					if (arr[99][j] == 2) {
						y = j;
					}
				}
			}


			while (x != 0) {					//맨 위에 갈 때 까지
				if (flag == 0) { // 상 
					if (y - 1 >= 0 && arr[x][y - 1] == 1) {
						y--;
						flag = 2;
					} else if (y + 1 <= 99 && arr[x][y + 1] == 1) {
						y++;
						flag = 1;
					} else {
						x--;
					}
				} else if (flag == 1) { // 우
					if (y + 1 <= 99 && arr[x][y + 1] == 1) {
						y++;
					} else {
						x--;
						flag = 0;
					}
				} else { // 좌
					if (y - 1 >= 0 && arr[x][y - 1] == 1) {
						y--;
					} else {
						x--;
						flag = 0;
					}
				}
			}

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

		}

	}
}