[SWEA] 1210 : Ladder1 - Java

1210

점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다.

김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다.

사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X표시에 도착하게 되는지 궁금해졌다. 이를 구해보자.

아래 <그림 1>의 예를 살펴보면, 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 개수의 막대들이 랜덤 간격으로 추가되고(이 예에서는 2개가 추가됨) 이 막대들 사이에 가로 방향의 선들이 또한 랜덤하게 연결된다.

X=0인 출발점에서 출발하는 사례에 대해서 화살표로 표시한 바와 같이, 아래 방향으로 진행하면서 좌우 방향으로 이동 가능한 통로가 나타나면 방향 전환을 하게 된다.

방향 전환 이후엔 다시 아래 방향으로만 이동하게 되며, 바닥에 도착하면 멈추게 된다.

문제의 X표시에 도착하려면 X=4인 출발점에서 출발해야 하므로 답은 4가 된다. 해당 경로는 별도로 표시하였다.

[제약 사항]

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

[입력]

입력 파일의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트 케이스가 주어진다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도착하게 되는 출발점의 x좌표를 출력한다.

코드

public class SWEA_1210_Ladder1 {

    static int[][] data = new int[100][100];
    static int n;
    static int dx[] = {0, 0, -1};
    static int dy[] = {-1, 1, 0};
    static int MAX_SIZE = 100;
    static int startPoint;
    static int a,b;  // 탐색 시작 위치
    static boolean flag;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for (int t = 1; t <= 10; t++) {
            n = Integer.parseInt(br.readLine());
            for (int i = 0; i < 100; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 100; j++) {
                    data[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            // 계산 과정
            // 일단 도착지점의 좌표 찾기
            int v = 0;
            for (int i = 0; i < 100; i++) {
                if (data[MAX_SIZE - 1][i] == 2) {
                    v = i;
                    a = MAX_SIZE-1;
                    b = i;
                    break;
                }
            }
            visited = new boolean[100][100];
            flag = false;
            // 중복 체크 , flag는 초기화 후에 계속 진행.
            DFS(a,b);
            System.out.println("#" + t + " " + startPoint);
        }
    }


    public static void DFS(int x, int y) {
        if(flag) return;
        if (x == 0) {
            flag = true;
            startPoint = y;
        } else {
            for (int i = 0; i < 3; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(isInner(nx, ny) && !visited[nx][ny] && data[nx][ny] == 1){ // 좌표 내부이면서, 좌표가
                    visited[nx][ny] = true; // 방문 처리 후
                    DFS(nx,ny);
                    visited[nx][ny] = false;
                }
            }
        }
    }

    public static boolean isInner(int x, int y) {
        if (x < 0 || x > MAX_SIZE - 1 || y < 0 || y > MAX_SIZE - 1) {
            return false;
        }
        return true;
    }
}

🎈 코멘트

현재 문제 사다리 타기 → 맨 위에서부터 시작하면 매우 오래 걸린다. 하지만 현재 도착지점은 정해져있는 상태. → 그렇기에 도착점에서부터 거꾸로 올라가는 방식을 선택하면 해당 문제를 쉽게 풀 수 있다. 나는 DFS로 풀었다.

1. 올라갈 때 주의사항은 무조건 왼쪽, 오른쪽을 위로 올라가는 것보다 우선으로 잡아야 한다.
   1. → 그렇게 하려면 dx,dy 값을 세팅할 때 왼쪽, 오른쪽 이후에 위로 올라가도록 배열을 세팅해야 한다.
2. DFS 이므로 이동한 좌표로 돌아가면 안되잖아. → 중복 체크 리스트 필요
3. 3가지 방향 모두 탐색하면서 y좌표 0에 도착하면 끝.
   1. 근데 끝나더라도 flag 변수에 true/false 걸어줘서 바로 끝나도록 설정해주기.

이 문제에서는 총 10만 반복하는데 나는 중복체크 배열, 찾았는지 확인 배열 모두 static

→ 매 반복문마다 초기화 해주기
배열 탐색에서 항상 생각해야 하는 것 → 해당 좌표 유효한지 체크.