[Java] SWEA 1211 Ladder2

1211 Ladder2 문제 링크

문제분석

• 사다리타기에서 모든 경로 중 가장 짧은 경로를 구하는 문제
• 최단거리로 도착하는 경로의 인덱스 구하기
  
  
• ‘0’ : 평면
• ‘1’ : 사다리

제약 사항

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

입력 조건

• 첫째 줄 : 테스트 케이스의 번호
• 둘째 줄 : 사다리 모양

출력 조건

• #부호 + 테스트 케이스 번호 + " " + 최단거리를 경로 출력

#1

import java.io.*;
import java.util.Scanner;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);

        for(int test_case = 1; test_case <= 10; test_case++)
        {
            int[][] arr = new int[100][100];
            int N = sc.nextInt();

            for(int i=0; i<100; i++) {
                for(int j=0; j<100; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }

            int[] countMin = {Integer.MAX_VALUE, 0};
            for(int i=0; i<100; i++) {
                int indexX = 0;
                int indexY = 0;
                if (arr[0][i]==1) {
                    int count = 0;
                    indexY = i;

                    while (indexX != 99) {
                        if (indexY != 0 && arr[indexX][indexY - 1] == 1) { //왼쪽 확인
                            while (indexY != 0 && arr[indexX][indexY - 1] == 1) {
                                indexY--;
                                count++;
                            }
                        } else if (indexY != 99 && arr[indexX][indexY + 1] == 1) { // 오른쪽 확인
                            while (indexY != 99 && arr[indexX][indexY + 1] == 1) {
                                indexY++;
                                count++;
                            }
                        }
                        indexX++; // 아래로 이동
                        count++;
                    }
                    if(count <= countMin[0]) {
                        countMin[1] = i;
                        countMin[0] = count;
                    }
                }
            }
            System.out.println("#" + N + " " + countMin[1]);
        }
    }
}

• 성공!
• 모든 경로를 지나가면서 계산하면 시간 초과가 날 줄 알았는데 통과됐다..?
• 따로 알고리즘 필요없이 구현만 하는 문젠가..