[1210] Ladder1

✔ Ladder1

[SWEA 1210]

문제 분석하기

배열에 숫자를 저장한 후 목적지부터 시작하여 위로 올라가며 시작점에 도달할 수 있는지 확인

손으로 풀어보기

1. 100 x 100 크기의 2차원 배열에 숫자 저장
2. 목적지에서 위로 올라가며 시작점을 찾음
   • 왼쪽이나 오른쪽으로 움직일 수 있다면 이동
   • 왼쪽이나 오른쪽으로 움직일 수 없다면 위로 이동
   • 위로 이동하면서 갔던 곳을 다시 가지 않도록 0으로 변경
3. x축의 인덱스가 0이 될 때까지 반복

슈도코드 작성하기

T(테스트 케이스 수) = 10
for(T만큼) {
    t(테스트 번호)
    ladder(사다리 숫자 저장 2차원 배열 (100 x 100 만큼))
    x, y(도착 위치)
    for(i -> ladder.lengthr만큼) {
        for (j -> ladder.length만큼) {
            ladder[i][j] = 입력 숫자 저장
            if (ladder[i][j] == 2) {
                도착 위치 저장
        }
    }
    dx, dy(왼쪽, 오른쪽, 위 방향)
    dx = {0, 0, -1}
    dy = {-1, 1, 0}
    while(x != 0) {
        for(3만큼) {
            nx, ny(왼쪽, 오른쪽, 위 방향에 따른 x, y 위치)
            if(사다리를 벗어나지 않는지) {
                if(이동할 수 있다면) {
                    갔던 곳을 다시 가지 않도록 0으로 변경
                    x, y를 이동 위치로 갱신
                }
            }
        }
    }
    #T와 출발점의 y 반환
}

코드 구현하기

/**
 * 1210) Ladder1
 */
public class D002_1210 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        // T(테스트 케이스 수) = 10
        int T = 10;
        // T만큼
        for (int test_case = 1; test_case <= T; test_case++) {
            // t(테스트 번호)
			int t = sc.nextInt();
            // ladder(사다리 숫자 저장 2차원 배열 (100 x 100 만큼))
            int[][] ladder = new int[100][100];
            // x, y(도착 위치)
            int x = 0, y = 0;
            // 사다리 숫자 저장
            for (int i = 0; i < ladder.length; i++) {
                for (int j = 0; j < ladder.length; j++) {
                    ladder[i][j] = sc.nextInt();
                    // 도착 위치 저장
                    if (ladder[i][j] == 2) {
                        x = i;
                        y = j;
                    }
                }
            }
            // dx, dy(왼쪽, 오른쪽, 위 방향)
            int[] dx = { 0, 0, -1 };
            int[] dy = { -1, 1, 0 };
            // 도착점에서부터 위로 올라가며 사다리 시작점을 찾음
            while (x != 0) {
                for (int j = 0; j < 3; j++) {
                    // nx, ny(왼쪽, 오른쪽, 위 방향에 따른 x, y 위치)
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    // 사다리를 벗어나지 않는지
                    if (nx >= 0 && nx < ladder.length && ny >= 0 && ny < ladder.length) {
                        // 이동할 수 있다면
                        if (ladder[nx][ny] == 1) {
                            // 갔던 곳을 다시 가지 않도록 0으로 변경
                            ladder[nx][ny] = 0;
                            // x, y를 이동 위치로 갱신
                            x = nx;
                            y = ny;
                        }
                    }
                }
            }
            // #T와 출발점의 y 반환
            System.out.println("#" + t + " " + y);
        }
    }
}