[SW Expert Academy] 1210 Ladder1 [Java]

[ EX TestCase ]

1

1 0 0 0 1 0 1 0 0 1

1 0 0 0 1 0 1 1 1 1

1 0 0 0 1 0 1 0 0 1

1 0 0 0 1 1 1 0 0 1

1 0 0 0 1 0 1 0 0 1

1 1 1 1 1 0 1 1 1 1

1 0 0 0 1 0 1 0 0 1

1 1 1 1 1 0 1 0 0 1

1 0 0 0 1 1 1 0 0 1

1 0 0 0 1 0 1 0 0 1

[ 핵심풀이 ]

0) 사다리에서 정답을 찾아가는게아닌, 정답에서 사다리출발점을 찾아가는것

1) 사다리가 놓인줄은 처음부터 끝까지 사다리가 이어져있다는점

1-1) 사다리가 놓인줄을 알 수 있는 리스트만들기

2) 위로한칸씩올라가며 좌우에 길이있는지 확인하고 길이있다면 현재 X축 위치를 변경 (-1, +1)

3) 범위 확인 잘하기

[ 핵심소스 ]

//왼쪽이 범위에벗어나지않고, 길이 존재할때
if (x - 1 > 0 && ary[y][x - 1] == 1) {
    nowidx -= 1;
    x = bridge.get(nowidx);
    q.add(new yx(y - 1, x));
    continue;
}
//오른쪽이 범위에벗어나지않고, 길이 존재할때
if (x + 1 < 100 && ary[y][x + 1] == 1) {
    nowidx += 1;
    x = bridge.get(nowidx);
    q.add(new yx(y - 1, x));
    continue;
}
q.add(new yx(y - 1, x));

[ Java ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class yx {
    int y;
    int x;
    yx(int y, int x) {
        this.y = y;
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
}

public class _1210_Ladder1 {
    static void init() throws NumberFormatException, IOException {
        int ary[][] = new int[100][100];

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int t = 1; t <= 10; t++) {
            int TC = Integer.parseInt(br.readLine());
            for (int i = 0; i < 100; i++) {
//          for(int i=0;i<10;i++) {
                String temp[] = br.readLine().split(" ");
                for (int k = 0; k < temp.length; k++)
                    ary[i][k] = Integer.parseInt(temp[k]);
            }
            System.out.print("#"+TC+" ");
            solve(ary);
        }
    }
    static void solve(int ary[][]) {
        ArrayList<Integer> bridge = new ArrayList<Integer>();
        Queue<yx> q = new LinkedList<yx>();
        int nowidx = 0;
        for (int t = 0; t < 100; t++) {
//      for(int t=0;t<10;t++) {
            if (ary[99][t] == 1)
                bridge.add(t);
            if (ary[99][t] == 2) {
                nowidx = bridge.size();
                bridge.add(t);
            }
        }
        q.add(new yx(99, bridge.get(nowidx)));
//      System.out.println(bridge.get(nowidx));
        while (!q.isEmpty()) {
            yx out = q.poll();
            int y = out.getY();
            int x = out.getX();
//          System.out.println(y + " " + x);
            if (y == 0) {
                System.out.println(x);
                break;
            }
            if (x - 1 > 0 && ary[y][x - 1] == 1) {
                nowidx -= 1;
                x = bridge.get(nowidx);
                q.add(new yx(y - 1, x));
                continue;
            }
            if (x + 1 < 100 && ary[y][x + 1] == 1) {
                nowidx += 1;
                x = bridge.get(nowidx);
                q.add(new yx(y - 1, x));
                continue;
            }
            q.add(new yx(y - 1, x));
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        init();
    }
}