[SWEA] 1210. Ladder1 (Java)

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

SW Expert Academy

 

풀이

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

public class Solution {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[][] arr = new int[100][100];
		int x = 0;


		for(int test =0; test<10; test++) {
			int t = Integer.parseInt(br.readLine());

			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[i][j] == 2) {
						x = j;
					}
				}
			}

			int i = 98;
			boolean left = true; // 왼쪽으로 갈 수 있는지
			boolean right = true; // 오른쪽으로 갈 수 있는지
			while(true) {
				// 목적지 도달
				if(i == 0) {
					break;
				}

				if (x>0) {
					// 왼쪽이 연결되어있으면
					if (arr[i][x-1] == 1 && left) {
						x--;
						right = false;
						continue;
					}
				}

				if(x<99) {
					// 오른쪽이 연결되어있으면
					if (arr[i][x+1] == 1 && right) {
						x++;
						left = false;
						continue;
					}
				}

				// 둘다 연결되어 있지 않다면
				i--;
				right = true;
				left = true;
			}
			System.out.println("#"+t+" "+x);
		}

		br.close();
	}
}

사다리타기는 출발지에서 출발하는 것이 아닌 도착점에서 출발해서 돌아오는 경로를 구하면

출발점을 한번에 구할 수 있다.

 

1. 사다리 배열 저장시 도착점의 위치를 구하기

일단 100 * 100 배열에 사다리 배열을 저장해준다.

 

위의 코드에서는 순회할때마다 도착점인지 판별했지만

도착점은 99번 인덱스 행에 있으므로

i가 99일때만 판별해도 된다.

2. 방향 정하기

도착점에서 한칸위는 무조건 연결되어 있을 것이므로

인덱스 98부터 시작하여

왼쪽으로 갈 수 있는지, 오른쪽으로 갈 수 있는지, 위로 가야하는지 여부를 판별한다.

 

또한 0열이거나 100열이면 왼쪽, 오른쪽으로 이동할 수 없으므로

x>0 , x<99 로 각각 체크해준다.

 

판별시 왼쪽으로 갔다가 다시 오른쪽으로 돌아오는 경우, 오른쪽으로 갔다 다시 왼쪽으로 돌아오는 경우를 방지하기 위해서

한번 이동한 경우 위로 가기전까진 반대방향으로 이동하지 못하도록 left, right 변수를 사용했다.

 

둘다 연결되어 있지않다면 인덱스를 -1 해주어 위로 이동시켜서, 인덱스가 0이 될 경우 목적지에 도달한 것이 된다.