1210번 - Ladder1

문제의 저작권은 SW Expert Academy에 있습니다. (출처)

1. 문제
   1-1. 문제 설명
   1-2. 문제 해석
2. 코드
3. 실행시간

 

 

 

---

 

1. 문제

1-1. 문제 설명

<그림 1> 사다리 게임에 대한 설명 (미니맵)

<그림 2> 테스트 케이스에 의해 생성되는 실제 사다리의 모습

 

 

1-2. 문제 해석

쉽게 말해 사다리 타기를 하는데 누가 당첨될지 맞춰보세요~ 하는 문제이다.

이 문제에서는 크게 두 가지 스킬 요구하고 있다.

 

1. 배열을 이용해서 이동하는 것을 구현할 수 있는가?
2. 맵을 벗어나는 상황을 잘 처리할 수 있는가?

이 두 가지를 중점으로 구현해나가면 된다.

그 외에 주의할 점은 다음과 같다.

 

출발지에서 위로 쭉쭉 올라가다가 왼쪽이나 오른쪽으로 갈 수 있는 칸에 도달하면 그쪽으로 이동한다라는 사실은 쉽게 생각해낼 수 있다.

문제는 옆으로 이동을 쭉쭉하다가 길이 끝나 다시 위로 올라가야 하는 때이다.

다시 위로 올라가야 하지만 그 상황에서 보면 왔던 길로 다시 되돌아갈 수 있는(= 옆으로 이동할 수 있는) 상황이므로 이 처리를 잘해주는 게 이 문제의 핵심이라고 생각한다.

나는 옆으로 가다가 길이 막히면 위로 한 칸 올라간 다음 다시 포문을 시작하는 방법으로 해결했다.

 

그다음으로는 나처럼 편견 속에 갇혀 있지 말라는 것이다.

나는 "사다리타기는 위에서 아래로 내려가는 거지!"라는 다소 멍청한 생각에 모든 출발지에서 출발해보며 당첨 도착지에 도착하는 지를 검사했다.

다른 동기들에 비해 속도가 꽤나 늦길래 뭐지 했는데 당첨 도착지에서 위로 올라가면 한 번만 사다리 타기를 하면 되는 문제였다... 🙄

 

 

2. 코드

public class Day2_1210_Ladder1 {
	static int[][] arr;
	static final int N = 100;
	static int y = 0;
	static int x = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		for (int tc = 1; tc <= 10; tc++) {
			br.readLine();
			arr = new int[N][N];
			int startIdx = Integer.MAX_VALUE;

			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.valueOf(st.nextToken());
					if (arr[i][j] == 2)
						startIdx = j;
				}
			}

			y = N - 1;
			x = startIdx;

			while (true) {
				if (!isUMovable()) {
					sb.append("#").append(tc).append(" ").append(x).append("\n");
					break;
				}
			}
		}

		System.out.println(sb.toString());
	}

	// 왼쪽로 이동이 가능한지 판단하고, 가능하다면 쭉 이동
	public static boolean isLMovable() {
		if (x == 0 || arr[y][x - 1] == 0) return false;
		while (x > 0 && arr[y][x - 1] == 1) x--;
		
		return true;
	}

	// 오른쪽로 이동이 가능한지 판단하고, 가능하다면 쭉 이동
	public static boolean isRMovable() {
		if (x == N - 1 || arr[y][x + 1] == 0) return false;
		while (x < N - 1 && arr[y][x + 1] == 1) x++;
		
		return true;
	}

	// 위로 이동이 가능한지 + 도착했는지 판단하고 이동
	public static boolean isUMovable() {
		while (y > 0 && isLMovable() == false && isRMovable() == false && arr[y - 1][x] == 1) y--;
		if (y == 0) return false; // 도착지에 도착한 경우

		y--; // 좌 혹은 우로 이동하다가 막힌 경우 아래로 한 칸 이동한다.
		return true;
	}
}

다소 지저분한 코드...

내가 작성했지만 좋은 답안은 아닌 것 같다.

 

 

3. 실행시간

3등 이예에ㅔㅔ

 

3등이긴 3등인데 실행시간이 굉장히 느리다. (불만족...)

그나저나 Java 1등 하신 분 코드 길이 365보고 놀라서 뒤로 자빠질 뻔했다.

아니 엄청 쉽고 간단한 문제도 저렇게 짧은 코드 길이는 못 봤는데??....

역대 싸피 선배들 중에서도 이 문제 코드 길이가 1100대인데 어떻게 365가 나온 건지... 미스테리다.

 

 

 

 

---

💡 느낀 점

• 세상은 넓고 알고리즘 괴물들은 많다
• 그저 길이 있는 곳으로만 따라가면 될 줄 알았던 사다리 타기였는데 실제로 구현해보니 생각해야 할 조건이 은근히 있었고 재밌었다.
• View 문제를 풀면서 멤버 변수를 활용해야겠다는 생각이 들었고, 이 문제에 적용시켜보았다. 어휴 안 썼으면 코드가 더 복잡해 보였을 듯

---