[SWEA] Ladder1 문제 풀이 및 설명 (Java)

안녕하세요~!
오늘은 SW Expert Academy의 Ladder1 문제를 풀이해보려 합니다.
난이도는 D4 이구요, 구현만 잘하면 어렵지 않게 풀 수 있는 문제입니다.
(는 저는 처음에 못풀었음,, )


그동안은 문제를 보자마자 달려들려고 했는데, 문제의 요구 사항 및 해결 전략을 간단히 세우고 나서 풀면 도움이 된다고 하시더라구요. 그래서 저도 앞으로는 정리를 간단히 해보고, 문제를 적어도 3번은 읽어보고 정확하게 접근하려고 합니다. 문제를 어렵게 풀었는데 정작 문제를 정확히 읽지 않아서 다 지우고 시작했던 적이 종종 있거든요.

문제는 아래 링크에서 확인해주세요! 😀

🍎 문제 링크

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

SW Expert Academy

 

🍏 문제 풀이 전략

먼저 이런 문제를 풀 때는 아래에서부터 출발하는 것이 좋습니다.
위에서부터 출발한다면 시작점과 탐색해야 할 경로들이 많지만, 아래에서 출발하게 되면 이미 도착점을 알고 있기 떄문에 한 가지의 경로만 잘 따라가다보면 답을 쉽게 구할 수 있게 됩니다.
다들 어렸을 때 사다리타기 게임에서 거꾸로 올라가본 적이 있으시죠? ㅎㅎ
마찬가지입니다.

그럼 풀이 전략을 세워보겠습니다. 

1. 마지막 행에서 2를 탐색하여 열(col) 정보를 저장한다.
2. 위로 이동하는데,  99행에서 0행까지 이동한다. 
    2-1) 왼쪽이 1인 경우 왼쪽으로 이동하는데, 다음칸이 경계를 넘어가거나 0일때까지 이동하다.
    2-2) 오른쪽이 1인 경우 오른쪽으로 이동하는데, 다음 칸이 경계를 넘어가거나 0일때까지 이동한다.
3. 시작 지점에 도착했다면(row가 0이라면) 이때의 열(col)을 출력한다.

정답 코드

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

public class Solution {
	static char[][] ladder = new char[102][102]; // 왜 대체 char 로 만들까? int가 더 편하지 않음?

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/recursion/input2.txt"));
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		// 위, 오, 왼 방향 델타이동
		int[] dr = { -1, 0, 0 };
		int[] dc = { 0, 1, -1 };

		// 방향 변수(0: 위, 1: 오른쪽, 2: 왼쪽)
		int direction = 0;

		for (int a = 0; a < 10; a++) { // 10번 반복, test case는 주어지므로 a 사용 안함
			// 입력 부분
			String tc = br.readLine();
			sb.append("#");
			sb.append(tc);
			sb.append(" ");

			int row = 100;
			int col = 100;

			for (int i = 1; i <= 100; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 1; j <= 100; j++) {
					ladder[i][j] = st.nextToken().charAt(0);
					// 값이 2일 경우 도착점 지정
					if (ladder[i][j] == '2') {
						row = i;
						col = j;
					}
				}
			}

			// 도착점부터 시작
			while (row > 1) {
				// 방향 분기 - 다른 방향 이동 가능할 경우 그 방향으로 변경
				// 좌, 우로 움직일 때
				if (direction != 0) {
					// 만약 위로 이동 가능하면 방향 위로 꺾음
					if (ladder[row - 1][col] == '1') {
						direction = 0;
					}
				} else {
					// 위로 올라가고 있을 때
					// 오른쪽으로 갈 수 있으면 방향 오른쪽으로 변경
					if (ladder[row][col + 1] == '1') {
						direction = 1;
					}
					// 왼쪽으로 갈 수 있으면 방향 왼쪽으로 변경
					if (ladder[row][col - 1] == '1') {
						direction = 2;
					}
				}
				
				// 이동 - 현재 방향으로 이동
				row += dr[direction];
				col += dc[direction];
			} // end of while
			
			sb.append(col - 1);
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}

}

개인적으로 moveLeft, moveRight라는 함수를 만들어서 사용한 부분이 좋았습니다.
main 메서드 안에서 모든 걸 하려니 굉장히 복잡해졌는데, 이렇게 하니 훨씬 깔끔하게 구현할 수 있더라구요.

아래에 다른 방식의 풀이를 추가할 예정입니다!