Geek's Village and Wells 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

1. 모든 W를 찾는다
2. W에 거리에 따라 H에 표시한다
3. N과 .의 경우, 0을 표시한다
4. N에 둘러쌓인 H의 경우 -1을 표시한다

H=8 H=6 H=4 H=6 H=8

H=6	H=4	H=2	H=4	H=6
H=4	H=2	W=0	H=2	H=4
H=6	H=4	H=2	H=4	H=6
H=8	H=6	H=4	H=6	H=8

W에 거리에 따라 H에 표시할때, 하나의 정점에서 시작해서 차례대로 연결된 정점을 하나씩 방문해서 거리를 표시하므로, 이는 문제에서 BFS (Breadth-First Search) 너비 우선 탐색을 사용하라는 것임을 알수 있습니다.

참고:

그래프 탐색: DFS,BFS 트리: inorder, preorder, postorder

시간복잡도: O(nm), 공간복잡도: O(nm)

class Solution {
    // 좌표값과 거리값을 담아둘 오브젝트
    static class Cell {
        int x, y, distance;

        Cell(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }

    public int[][] chefAndWells(int n, int m, char[][] c) {
        // 결과값을 담아둘 2D 어레이
        int[][] result = new int[n][m];
        //상하좌우 검색을 위한 어레이
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        //방문을 하기 위한 리스트가 담긴 큐
        Queue<Cell> queue = new LinkedList<>();
        // 방문한 셀을 표시하기 위한 2D 어레이
        boolean[][] visited = new boolean[n][m];

        // 모든 W를 큐에 추가하고 방문 표시를 합니다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (c[i][j] == 'W') {
                    queue.offer(new Cell(i, j, 0));
                    visited[i][j] = true;
                }
            }
        }

        // 큐가 빌 때까지 BFS를 실행합니다.
        while (!queue.isEmpty()) {
            Cell current = queue.poll();

            // 현재 셀이 집인 경우, 결과 배열에 거리의 두 배를 저장합니다.(왕복)
            if (c[current.x][current.y] == 'H') {
                result[current.x][current.y] = current.distance * 2;
            }

            // 현재 셀의 상하좌우 셀을 확인합니다.
            for (int i = 0; i < 4; i++) {
                int newX = current.x + dx[i];
                int newY = current.y + dy[i];

                // 1. 상하좌우 셀이 존재하며,
                // 2. 방문하지 않았으며,
                // 3. 'N'이 아닌 경우,
                // 큐에 추가하고 방문 표시를 합니다.
                if (isValidMove(newX, newY, n, m) && !visited[newX][newY] && c[newX][newY] != 'N') {
                    queue.offer(new Cell(newX, newY, current.distance + 1));
                    visited[newX][newY] = true;
                }
            }
        }

        // 결과 배열을 순회하며 N,W,.과 N에 둘러쌓인 H값을 조정합니다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 집이 우물에 도달할 수 없는 경우 결과 값을 -1로 설정합니다.
                if (c[i][j] == 'H' && result[i][j] == 0) {
                    result[i][j] = -1;
                }
                // 집이 아닌 경우 (즉, 'N', 'W', '.') 결과 값을 0으로 설정합니다.
                else if (c[i][j] != 'H') {
                    result[i][j] = 0;
                }
            }
        }

        return result;
    }

    // 상하좌우 셀이 존재하는가 확인.
    private boolean isValidMove(int x, int y, int n, int m) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
}