[SWEA/Java] 1210. Ladder1 : 재귀로 풀기

[SWEA/Java] 1210. Ladder1 : 재귀로 풀기

SW Expert Academy

---

풀이

package edu.ssafy.im.SWEA.D4.No1210;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_Recursive {
    int[][] direction = { { 0, 1 }, { 0, -1 }, { -1, 0 } }; // 오른쪽, 왼쪽, 위쪽으로 이동하는 방향
    int[][] graph; // 사다리 정보를 담을 배열
    int ax, ay; // 도착점의 좌표
    boolean[][] visited; // 방문 여부를 체크할 배열

    public static void main(String[] args) throws IOException {
        new Solution_Recursive().sol();
    }

    private void sol() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int testCase = 10; // 총 테스트 케이스 수

        for (int t = 1; t <= testCase; t++) {
            br.readLine(); // 테스트 케이스 번호는 사용하지 않으므로 읽지 않음
            graph = new int[100][100]; // 사다리 정보 배열 초기화
            for (int x = 0; x < graph.length; x++) {
                String row = br.readLine();
                StringTokenizer st = new StringTokenizer(row);
                for (int y = 0; y < graph.length; y++) {
                    graph[x][y] = Integer.parseInt(st.nextToken()); // 사다리 정보 입력
                    if (graph[x][y] == 2) { // 도착점의 좌표 저장
                        ax = x;
                        ay = y;
                    }
                }
            }

            visited = new boolean[100][100]; // 방문 여부 배열 초기화
            sb.append("#").append(t).append(" ").append(dfs(ax, ay)).append("\n"); // 출발점의 x 좌표를 출력하기 위해 dfs 호출
        }
        System.out.println(sb);
    }

    private int dfs(int x, int y) {
        // 기본 파트: 출발점에 도착한 경우 해당 출발점의 x 좌표 반환
        if (x == 0)
            return y;

        // 재귀 파트
        for (int d = 0; d < 2; d++) { // 왼쪽과 오른쪽 방향으로 이동
            int nx = x + direction[d][0];
            int ny = y + direction[d][1];

            if (checkStatus(nx, ny)) { // 이동할 수 있는 상태인지 확인
                visited[x][y] = true; // 방문 표시
                return dfs(nx, ny); // 다음 위치로 이동하여 재귀 호출
            }
        }
        // 위쪽 방향으로 이동
        int nx = x + direction[2][0];
        int ny = y + direction[2][1];
        return dfs(nx, ny); // 다음 위치로 이동하여 재귀 호출
    }

    private boolean checkStatus(int x, int y) {
        // 배열 범위 내에 있고, 방문하지 않았고, 사다리가 있는 위치인지 확인
        return (0 <= x && x < 100 && 0 <= y && y < 100 && !visited[x][y] && graph[x][y] == 1);
    }
}