문제

문제 바로 가기

문제 풀이

문제 조건중 한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다. 라는 조건 덕에, 복잡한 케이스 고려X
사다리 맨 마지막의 도착지로부터 역으로 추적
현재 이동 방향을 표시하는 direction변수를 사용하여 유동적으로 방향 전환
- 현재 방향이 위로 향하는 경우
  - 위로 향하던 도중, 양 옆에 길이 있으면 그 길로 빠져야함
    - 가로선이 다른 막대를 가르는 경우는 없기 때문에, 왼쪽 또는 오른쪽 길이 발견되면 바로 그쪽 길로 향하면 됨
    - update direction
  - 옆의 길이 발견되지 않으면 계속 위로 이동
- 현재 방향이 오른쪽으로 향하는 경우
  - 현재 위치의 오른쪽에 길이 있으면 계속 오른쪽으로 이동
  - 길이 막히면 위로 이동, update direction
- 현재 방향이 왼쪽으로 향하는 경우
  - 마찬가지로, 왼쪽에 길이 있으면 계속 왼쪽으로 이동
  - 길이 막이면 위로 이동, update direction

코드

/*
X에서부터 역으로 검사
*/
import java.util.*;
import java.io.FileInputStream;

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

        // 입력
        for(int test_case = 1; test_case <= 10; test_case++)
        {
            int[][] arr = new int[100][100];
            int dest = 0;
            for (int i = 0; i < 100; i++){
                for (int j = 0; j < 100; j++){
                    arr[i][j] = sc.nextInt();
                    // 도착지 검색
                    if (i == 99 && arr[i][j] == 2)    dest = j;
                }
            }

            int i = 100;
            int j = dest;

            // direction: 검사하던 방향
            // 0: i-1
            // 1: j-1
            // 2: j+1
            int direction = 0;
            // 목적지에서 부터 탐색
            while (i >= 0){
                // 위로 이동 중
                if (direction == 0){
                    // 양 옆으로 빠질 수 있으면 빠짐
                    if (i <= 99 && j-1 >= 0 && arr[i][j-1] == 1){
                        j--;
                        direction = 1;
                    }
                    else if (i <= 99 && j+1 <= 99 && arr[i][j+1] == 1){
                        j++;
                        direction = 2;
                    }
                    // 옆에 길이 없으면 계속 올라감
                    else    i--;
                }
                // 왼쪽으로 이동 중
                else if (direction == 1){
                    // 왼쪽으로 길이 있으면 계속 이동
                    if (j-1 >= 0 && arr[i][j-1] == 1)    j--;
                        // 길이 없으면 위로 올라감
                    else{
                        i--;
                        direction = 0;
                    }
                }
                // 오른 쪽으로 이동 중
                else if (direction == 2){
                    // 오른쪽으로 길이 있으면 계속 이동
                    if (j+1 <= 99 && arr[i][j+1] == 1)    j++;
                        // 길이 없으면 위로 올라감
                    else{
                        i--;
                        direction = 0;
                    }
                }
            }

            System.out.printf("#%d %d\n", test_case, j);

            try{sc.nextInt();}catch(Exception e){}}
    }
}

실행 결과

느낀 점

해결 로직은 쉽게 떠올렸으나, i를 업데이트 하는 부분에서 오타가 발생해서 해맴