[코드트리/INTERMEDIATE LOW] 두 방향 탈출 가능 여부 판별하기 (JAVA)

📖 문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• DFS

(0, 0)에서부터 DFS 탐색을 시작한다.

 

해당 위치의 아래, 오른쪽 방향을 탐색하며

1) 격자 범위를 벗어나지 않고, 2)  방문한 적 없고, 3) 뱀이 없다면

해당 위치로 이동한다.

 

(N -1, M -1) 위치를 방문한 적 없다면 0을, 방문하였다면 1을 출력하도록 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {1, 0};   // 아래, 오른쪽
    static int[] dy = {0, 1};
 
    static int N, M;
    static int[][] grid;
    static boolean[][] visited;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        grid = new int[N][M];
 
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < M ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        visited = new boolean[N][M];
        dfs(0, 0);
 
        System.out.println(visited[N - 1][M - 1] ? 1 : 0);
    }
 
    private static void dfs(int x, int y) {
        visited[x][y] = true;    // 탐색 시작 전 해당 위치 방문했음 미리 표시
 
        for(int d = 0 ; d < 2 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if(canGo(nx, ny)) {
                dfs(nx, ny);
            }
        }
    }
 
    private static boolean canGo(int x, int y) {
        if(!inRange(x, y) || visited[x][y])  return false;
        if(grid[x][y] == 0) return false;
        return true;
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
}

 

 

 

➕ 다른 풀이 방식

visited 방문 배열을 boolean형으로 안 만들고, int형으로 만든다.

해당 위치를 방문했을 때는 1로 만들면 되고, grid[N - 1][M - 1]을 출력해주면 된다.

 

---

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리

그리드 상에서의 DFS 탐색 - 인접 리스트/행렬 필요 X