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

📖 문제

 

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

 

 

💡  풀이 방식

• BFS

필요 자료구조
- 인접 4방향 탐색용 dx/dy 배열
- 숫자 입력받을 2차원 int형 배열 (grid)
- 방문 여부 표시할 2차원 int형 배열 (visited)
- 방문하는 칸 위치 저장할 Queue

 

(0, 0)부터 BFS를 수행한다.

 

BFS 수행 시, 큐에 해당 위치 좌표를 저장하고, 방문 처리(visited[x][y] = 1)한다.

위치를 저장한 큐가 모두 빌 때까지 큐에서 위치를 뽑는다.

 

뽑은 위치의 인접 4방향을 탐색하며

1) 격자 범위를 벗어나지 않고 2) 방문한 적 없고 3) 뱀이 아닌 경우 (1인 경우)

해당 좌표에서 다음 탐색을 진행하도록 그 위치 값을 큐에 저장한다.

 

탈출 가능한 경로가 있다면 맨 오른쪽 아래 칸의 값도 1일 것이며,

없다면 맨 오른쪽 아래 칸의 값은 0일 것이므로

맨 오른쪽 아래 칸의 값을 그대로 출력한다.

(문제 조건에 끝 칸에는 뱀이 주어지지 않는다고 가정한다 하였으므로 가능)

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    static int N, M;
    static int[][] grid;
    static int[][] 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 int[N][M];
        bfs(0, 0);
 
        System.out.println(visited[N- 1][M - 1]);
    }
 
    private static void bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
 
        visited[x][y] = 1;
 
        while(!q.isEmpty()) {
            int[] now = q.poll();
 
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
 
                if(canGo(nx, ny)) {
                    q.add(new int[] {nx, ny});
                    visited[nx][ny] = 1;
                }
            }
        }
    }
 
    private static boolean canGo(int x, int y) {
        if(!inRange(x, y))  return false;
        if(visited[x][y] == 1 || 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);
    }
}

 

 

---

 

 

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