[SWEA-1210] Ladder1 - Java

사다리를 타서 2가 걸리는 시작지점이 어딘지를 찾는 문제입니다.

밑에서 2를 찾아서 올라가는 방식으로 구했습니다. 한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하는 경우가 없기 때문에 왼쪽, 오른쪽, 위의 순서로 방향을 봐주면서 다음 좌표를 업데이트해주면 됩니다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Ladder1 {
	static int size = 100;
	
	private static boolean isIn(int y, int x) {
		if(0<= y && y < size && 0<= x && x < size) return true;
		else return false;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String output = "";
		int[] dy = {0, 0, -1};
		int[] dx = {1, -1, 0};
		
		int T;
		T=10;
		
		for(int test_case = 1; test_case <= T; test_case++) {
			int n = sc.nextInt();
			int [][] ladder = new int[size][size];
			boolean [][] checked = new boolean[size][size];
			
			for(int i = 0; i< size;i++) 
				for(int j = 0; j<size;j++)
					ladder[i][j] = sc.nextInt();
			
			for(int i = 0; i<size;i++) {
				if(ladder[size-1][i] == 2) {
					int cy = size-1;
					int cx = i;
					int ny = size;
					int nx = size;
					
					while(ny != 0) {
						for(int j = 0; j< 3; j++) {
							ny = cy + dy[j];
							nx = cx + dx[j];
							if(!isIn(ny, nx)) continue;
							if(ladder[ny][nx] == 1 && !checked[ny][nx]) {
								cy = ny;
								cx = nx;
								checked[cy][cx] = true;
								break;
							}
						}					
					}
					
					output += "#" + test_case + " " + nx + "\n";
					
					break;
				}
			}
			
		}
		System.out.println(output);
	}
}

 

 

if(ladder[ny][nx] == 1 && !checked[ny][nx]) {
	cy = ny;
	cx = nx;
	checked[cy][cx] = true;
	break;
}

이미 왔던 길을 체크하기 위해서 checked 변수를 두어서 체크해주고, 갈 수 있는 방향만 찾으면 다른 방향을 볼 필요가 없숩니다.

 

D4라길래 쫄았는데 요건 D4중에 젤 쉬운 문제인거 같슴니다.

 

감사함니다 ^3^