[JAVA] SWEA 1210번 Ladder1

문제

점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다.

김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다.

사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X표시에 도착하게 되는지 궁금해졌다. 이를 구해보자.

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

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

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

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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh&categoryId=AV14ABYKADACFAYh&categoryType=CODE

SW Expert Academy

 

제약 사항

한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다.

입력

입력 파일의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트 케이스가 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도착하게 되는 출발점의 x좌표를 출력한다.

풀이1

입력값을 모두 받은 후, 위에서 아래로 사다리를 타며 2를 찾는 방법으로 코드를 작성하였다.

 

y++을 하며 아래로 한칸씩 이동하다가, 좌우의 1을 발견하면 flag를 left, right로 바꾸고 해당 방향으로 이동한다.

 

좌우에 1이 없을 경우 아래로 이동한다.이를 반복하다가 2를 발견하면 루프를 멈추고 정답을 출력한다.

 

import java.util.Scanner;

class Ladder1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int left = 1, right = 2, down = 3;
		
		for (int test_case = 1; test_case <= 10; test_case++) {
			int tc = sc.nextInt();
			int [][] ladders = new int[100][100];
			int answer = 0;
			int flag = 0;
			
			for (int i = 0; i < 100; i++) {
				for (int j = 0; j < 100; j++) {
					ladders[i][j] = sc.nextInt();
				}
			}
			
			for (int i = 0; i < ladders.length; i++) {
				int x = i, y = 0;
				flag = down;
				if (ladders[0][i] == 1) {
					y++;
					while (y < 100) {
						if (ladders[y][x] == 2) {
							answer = i;
							break;
						}
						if (flag == down) {
							if (x-1 >= 0 && ladders[y][x-1] == 1) {
								x--;
								flag = left;
							} else if (x+1 < 100 && ladders[y][x+1] == 1) {
								x++;
								flag = right;
							} else {
								y++;
								flag = down;
							}
						} else if (flag == right) {
							while(x < 100 && ladders[y][x] == 1) {
								x++;
							}
							x--;
							y++;
							flag = down;
						} else {
							while (x >= 0 && ladders[y][x] == 1) {
								x--;
							}
							x++;
							y++;
							flag = down;
						}
					}
				}
			}
			
			System.out.println("#" + tc + " " + answer);
		}
	}
}

 

풀이2

2로부터 위로 사다리를 타고 올라가는 방법으로 코드를 작성하였다.

입력을 받는 시점에 2를 검사하여 위치를 저장한다.

위의 풀이와 마찬가지로 한칸씩 이동하며 사다리를 탄다.

끝까지 올라갔을 경우 그 자리의 x좌표의 값을 정답으로 출력한다.

import java.util.Scanner;

class Ladder1_v2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int left = 1, right = 2, up = 3;
		int x = 0, y = 0;
		
		for (int test_case = 1; test_case <= 10; test_case++) {
			int tc = sc.nextInt();
			int [][] ladders = new int[100][100];
			int flag = up;
			
			for (int i = 0; i < 100; i++) {
				for (int j = 0; j < 100; j++) {
					ladders[i][j] = sc.nextInt();
					if (ladders[i][j] == 2) {
						y = i-1;
						x = j;
					}
				}
			}
			
			while(y > 0) {
				if (flag == up) {
					if (x-1 >= 0 && ladders[y][x-1] == 1) {
						x--;
						flag = left;
					} else if (x+1 < 100 && ladders[y][x+1] == 1) {
						x++;
						flag = right;
					} else {
						y--;
					}
				}
				else if (flag == right) {
					if (x+1 < 100 && ladders[y][x+1] == 1) {
						x++;
					} else {
						y--;
						flag = up;
					}
				}
				else {
					if (x-1 >= 0 && ladders[y][x-1] == 1) {
						x--;
					} else {
						y--;
						flag = up;
					}
				}
			}
			
			System.out.println("#" + tc + " " + x);
		}
	}
}

 

두번째 풀이가 성능이 훨씬 좋을거라 생각했는데, 결과는 비슷했다.

이유가 무엇인가 생각해보았는데,

아무래도 인풋과정에서 계속해서 값이 2인지 검사하는 과정이 성능에 영향을 주지 않았나 생각한다.