도시와 비트코인

https://www.acmicpc.net/problem/31575

문제

전날에 비해 비트코인의 시세가 백만원이나 오른 어느 아침, 진우는 거래소에 가서 비트코인을 매도하려고 한다. 현재 비트코인의 시세가 점점 떨어지고 있기 때문에 진우는 최대한 빨리 거래소에 가야 한다.
도시는 가로
$N$, 세로
$M$ 크기의 격자 모양으로 이루어졌다. 진우는 북서쪽 끝에 있고 거래소는 남동쪽 끝에 있다. 도시의 일부 구역은 공터 또는 도로라서 진우가 지나갈 수 있지만, 어떤 구역은 건물이 있어서 진우가 갈 수 없다.
진우는 최대한 빨리 거래소에 가야 하므로, 동쪽(오른쪽) 또는 남쪽(아래쪽)으로만 이동하여 거래소로 도착할 수 있어야 한다. 진우를 도와 거래소로 갈 수 있는지 구하는 프로그램을 작성하여라. 진우의 현재 위치가 거래소일 수 있다.

입력

첫 번째 줄에 도시의 가로 크기
$N$과 세로 크기
$M$ (
$1 \le N, M \le 300$)이 주어진다.
두 번째 줄부터
$M$개의 줄에는 도시의 형태를 나타내는
$N$개의 정수가 공백을 사이에 두고 주어진다. 각 칸이 1인 경우 진우가 갈 수 있는 칸을 의미하고 0인 경우 진우가 갈 수 없는 칸을 의미한다.
왼쪽 위의 끝 칸과 오른쪽 아래의 끝 칸은 모두 1이다.

출력

첫 번째 줄에 진우가 거래소로 갈 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

예제

5 4
1 1 1 1 1
0 1 0 0 1
1 0 0 0 1
0 0 0 1 1

-> YES

어떻게 풀까?

dfs를 활용하여 방문처리와 함께 경로 탐색

gpt 구현

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

public class Main {

    static int n, m;
    static int[][] road;
    static boolean[][] visited;

    static int[] dx = {1, 0};	// 방향 배열(동, 남)
    static int[] dy = {0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stoi = new StringTokenizer(read.readLine());
        n = Integer.parseInt(stoi.nextToken());
        m = Integer.parseInt(stoi.nextToken());

        road = new int[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            StringTokenizer stoiLoad = new StringTokenizer(read.readLine());
            for (int j = 0; j < n; j++) {
                road[i][j] = Integer.parseInt(stoiLoad.nextToken());
            }
        }
        if (dfs(0,0)){
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }
    }



    public static boolean dfs(int x, int y) {	// dfs 알고리즘
        visited[x][y] = true;	// 방문한 배열은 true 저장
        for(int i = 0; i < 2; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX >= 0 && nextY >= 0 && nextX < m && nextY < n && !visited[nextX][nextY]) {	// 범위 내에 있고 방문한 적이 없으면
                if(road[nextX][nextY] == 1) {	// 배열 값이 1이면
                    dfs(nextX, nextY);	// dfs 호출
                }
            }
        }
        return visited[m-1][n-1];	// 거래소 방문여부 리턴
    }
}

첫번째 풀이

    static boolean dfs(int x, int y) {
        //도착 지점에 도착했는가?
        if(x == m-1 && y == n-1){
            return true;
        }
        //주어진 지도에서 벗어났는가?
        if(x >= m || y >= n){
            return false;
        }
        //오른쪽, 아랫쪽 1인 길로 가서 dfs 함수 재귀호출
        if (road[x + 1][y] == 1) {
            dfs(x + 1, y);
        } else if (road[x][y + 1] == 1) {
            dfs(x, y + 1);
        }
        return false;
    }

방문처리가 안됨, 잘못 갔을 경우 돌아올 수 없다

두번째 풀이

static boolean dfs(int x, int y) {
    // 종료 조건: 목적지 도달 시 true 반환
    if (x == n - 1 && y == m - 1) {
        return true;
    }

    // 범위를 벗어나거나 이동할 수 없는 위치일 경우 false 반환
    if (x < 0 || x >= n || y < 0 || y >= m || road[x][y] == 0 || visited[x][y]) {
        return false;
    }

    // 현재 위치를 방문 처리
    visited[x][y] = true;

    // 동쪽 또는 남쪽으로 이동하며 DFS 재귀 호출
    if (dfs(x + 1, y) || dfs(x, y + 1)) {
        return true;
    }

    // 방문 취소
    visited[x][y] = false;
    return false;
}

범위를 벗어나거나 이동할 수 없는 위치일 경우 false 반환 이 조건에서 false를 반환할 것이 아니라 그 뒤로 돌아가서 다시 탐색이 안 되는것 같다.
다시 어떻게 뒤로 돌아가지?

재귀함수 모르겠다! 스택 사용

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

public class Main {

    static int n, m;
    static int[][] road;
    static boolean[][] visited;

    static int[] dx = {1, 0};    // 방향 배열(동, 남)
    static int[] dy = {0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stoi = new StringTokenizer(read.readLine());
        n = Integer.parseInt(stoi.nextToken());
        m = Integer.parseInt(stoi.nextToken());

        road = new int[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            StringTokenizer stoiLoad = new StringTokenizer(read.readLine());
            for (int j = 0; j < n; j++) {
                road[i][j] = Integer.parseInt(stoiLoad.nextToken());
            }
        }
        if (dfsIterative(0, 0)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    public static boolean dfsIterative(int startX, int startY) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[] {startX, startY});
        visited[startX][startY] = true;

        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            int x = current[0];
            int y = current[1];

            // 목적지 도달 여부 확인
            if (x == m - 1 && y == n - 1) {
                return true;
            }

            // 동쪽 및 남쪽 방향으로 이동할 수 있는지 확인
            for (int i = 0; i < 2; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];

                // 유효한 위치이고, 방문하지 않았으며, 도로(1)인 경우 스택에 추가
                if (nextX >= 0 && nextY >= 0 && nextX < m && nextY < n && !visited[nextX][nextY] && road[nextX][nextY] == 1) {
                    stack.push(new int[] {nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }

        return false;  // 스택이 비었으나 목적지에 도달하지 못한 경우
    }
}

1인 곳에 가면 스택에 push 하고 이후에 들어간 방향의 스택에서 1인 쪽의 경로가 없을때 까지 탐색한다
오른쪽, 아래쪽 모두 1일때 이후에 push된 경로로 탐색하다가 경로가 없어서 push하지 못하면 그때 양쪽 모두 들어갔을때의 요소로 다시 탐색한다.