SWEA 1210 2일차 - Ladder1

import java.util.Scanner;

class Ladder
{
    static int[][] map;
    static boolean[][] visited;
    static int[] dr = {0,0,-1};
    static int[] dc = {1,-1,0};
    static int test;
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=10;
        map = new int[100][100];

        int initrow = 0;
        int initcol = 0;
        for(int test_case = 1; test_case <= T; test_case++)
        {
            visited = new boolean[100][100];
            test = sc.nextInt();
            for(int i = 0; i < 100; i++){
                for(int j = 0; j<100; j++){
                    map[i][j] = sc.nextInt();
                    if(map[i][j]==2){
                        initrow = i;
                        initcol = j;
                    }
                }
            }
            recursion(initrow,initcol);
        }
    }
    public static void recursion(int row, int col){
        if(row == 0){
            System.out.println("#"+test+" "+col);
            return;
        }
        for(int i = 0; i<3; i++){
            int nrow = row + dr[i];
            int ncol = col + dc[i];
            if(nrow <0||ncol<0||nrow>=100||ncol>=100)
                continue;
            if(!visited[nrow][ncol]&&map[nrow][ncol]==1){
                visited[nrow][ncol]=true;
                recursion(nrow,ncol);
                break;
            }
        }
    }
}

풀이방법

이 문제는 특이하게 도착지점을 주고, 시작지점을 구하는 문제이다.
구현 방법은 두가지를 생각해볼 수 있는데,
1. 모든 시작지점을 완전탐색 방식으로 넣어서 도착지점이 나오는 경우의 수를 찾기
2. 도착지점부터 거꾸로 올라가서 시작지점을 찾기

👉 간단하게 2번 방식을 구현할 수 있다면 좋겠지만, 생각해내거나, 조건이 까다로울 수 있으므로 두 가지 방식 모두를 고려하는것이 좋다.
이 문제에서는 2번 방식으로 구현하였다.

1. 도착지점의 row,col을 재귀함수에 넣는다.
2. 사다리는 갈림길에서 좌,우 먼저 탐색 후 아래로 내려가기 때문에 dr, dc를 좌,우먼저 탐색하도록 설정하고 탐색을 시작한다.
3. 한번 이동했다면 다시 되돌아오지는 않으므로, break를 통해 반복을 빠져나온다.
4. col==0이 되는 지점에서 출력해준다.