SEWA 1210번 [S/W 문제해결 기본] 2일차 - Ladder1

1210번 [S/W 문제해결 기본] 2일차 - Ladder1 D4

문제

난이도

• D4

풀이

사다리의 도착 지점으로 향하는 출발 지점 찾기

도착 지점은 한 개로 정해져 있기 때문에 도착지점부터 위로 올라가며 출발지점을 찾는다.

갈림길이 나왔을 때 방향을 선택하기

지나온 경로를 확인할 방법이 필요하다.

코드

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

// 1210번, [S/W 문제해결 기본] 2일차 - Ladder1 D4
public class Solution {

    public static final int len = 100;

    public static int[] dx = { 0, 0, -1 }; // 좌 - 0, 우 - 1, 상 - 2
    public static int[] dy = { -1, 1, 0 };

public static void main(String[] args) throws IOException {

        // System.setIn(new FileInputStream("input.txt"));

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        int T = 10; // test_case 개수

        for (int t = 1; t <= T; t++) {
            int test_case = Integer.parseInt(in.readLine());

            sb.append("#" + test_case + " ");

            int[][] map = new int[len][len];

            int ans = -1;

            for (int i = 0; i < len; i++) {
                StringTokenizer st = new StringTokenizer(in.readLine());
                for (int j = 0; j < len; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            loop: for (int col = 0; col < len; col++) {
                int row = len - 1;

                if (map[row][col] != 2) {     // 도착점에서 출발점으로 가는 경로 탐색
                    continue;                // 도착점 기준 아래에서 위로 탐색
                }

                int newRow = row;
                int newCol = col;
                int direction = 2;

                while (true) {
                    if (newRow == 0) {     // 최상단(출발점)에 도착했을 때 전체 반복문 종료
                        ans = newCol;     // 출발점의 열(column)
                        break loop;
                    }
                    for (int idx = 0; idx < 3; idx++) {

                        // 한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다.
                        // 방향을 확인하는 방법 or 지나온 길을 다른 값으로 바꾸는 방법(추천)

                        // 방향을 확인하는 방법
                        if (direction == 0 && idx == 1) { // 지나온 방향은 탐색하지 않는다.
                            continue;
                        }

                        if (direction == 1 && idx == 0) { // 지나온 방향은 탐색하지 않는다.
                            continue;
                        }

                        if ((newRow + dx[idx]) < 0 || (newRow + dx[idx]) > len - 1 || (newCol + dy[idx]) < 0
                                || (newCol + dy[idx]) > len - 1) {
                            continue; // 사다리 경계를 벗어난 경우
                        }

                        if (map[newRow + dx[idx]][newCol + dy[idx]] == 1) { // 사다리가 존재하는 경우
                            direction = idx;
                            newRow += dx[idx];
                            newCol += dy[idx];
                            break;
                        }
                    }
                }
            }
            sb.append(ans + "\n");
        }
        out.write(sb.toString());
        out.close();
    }
}

OpenJDK8 Azul Zulu 8.33.0.1

Eclipse Java EE IDE 2018-09R