거리두기 확인하기 (프로그래머스, Java)

https://school.programmers.co.kr/learn/courses/30/lessons/81302?language=java#fnref1 

프로그래머스

 

 

BFS의 흐름은 거의 정석화되어 있기 때문에 BFS의 코드를 완벽히 외우는 것이 가장 중요하다.

 

import java.util.*;

class Solution {
    class Point {
        int row, col, dist;
        
        Point(int row, int col, int dist) {
            this.row = row;
            this.col = col;
            this.dist = dist;
        }
    }
    int[][] D = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    
    boolean bfs(String[] place, int row, int col) {
        boolean[][] visited = new boolean[5][5];

        Queue<Point> q = new LinkedList<>();
        visited[row][col] = true;
        q.add(new Point(row, col, 0));
        
        while (!q.isEmpty()) {
            Point curr = q.remove();
            
            if (curr.dist > 2) continue;
            if (curr.dist != 0 && place[curr.row].charAt(curr.col) == 'P') {
                return false;
            }
            
            for (int i = 0; i < 4; i++) {
                int newRow = curr.row + D[i][0];
                int newCol = curr.col + D[i][1];
                
                if (newRow < 0 || newRow > 4 || newCol < 0 || newCol > 4) continue;
                if (visited[newRow][newCol]) continue;
                if (place[newRow].charAt(newCol) == 'X') continue;
                visited[newRow][newCol] = true;
                q.add(new Point(newRow, newCol, curr.dist + 1));
            }
        }
        return true;
    }
    
    boolean check(String[] place) {
        
        for (int row = 0; row < 5; row++) {
            for (int col = 0; col < 5; col++) {
                if (place[row].charAt(col) == 'P') {
                    if (!bfs(place, row, col))
                        return false;
                }
            }
        }
        return true;
    }
    
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        for (int i = 0; i < 5; i++) {
            if (check(places[i])) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }
        return answer;
    }
}

 

정답의 길이가 정해져있기 때문에 배열의 크기를 지정하면서 선언을 먼저 한다.

 

사실상 3차 배열의 문제였기 때문에(String[][] 배열 안의 String[] 배열 안의 charArray)

String[][] 배열을 돌며 String[] 배열을 하나씩 조건 체크를 하며 정답 배열에 값을 채워넣는다고 가정한다.

아직까지 메서드의 내부 구현은 되어있지 않다.

 

    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        for (int i = 0; i < 5; i++) {
            if (check(places[i])) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }
        return answer;
    }

 

String[]이 2차 배열은 아니지만 2차 배열로 사용되었기 때문에

2중 for loop를 돌며 조건 체크를 한다.

이 문제의 경우 해당 char가 'P'일 경우 맨해튼 거리 내에 다른 P가 있는지 확인해야 하기에

'P'를 찾으면 BFS 탐색을 실시한다.

 

이때 bfs에는 현재 String과 x,y좌표를 보낸다.

 

    boolean check(String[] place) {
        
        for (int row = 0; row < 5; row++) {
            for (int col = 0; col < 5; col++) {
                if (place[row].charAt(col) == 'P') {
                    if (!bfs(place, row, col))
                        return false;
                }
            }
        }
        return true;
    }

 

X, Y좌표인 int row, int col과 시작 위치로부터의 거리를 받는 int dist를 파라미터로 받는 Point 객체를 선언한다.

그리고 맨해튼 거리를 측정하는 것이므로 상,하,좌,우로 움직이는 행동을 미리 정의한 D값을 선언한다.

 

    class Point {
        int row, col, dist;
        
        Point(int row, int col, int dist) {
            this.row = row;
            this.col = col;
            this.dist = dist;
        }
    }
    int[][] D = {{1,0}, {-1,0}, {0,1}, {0,-1}};

 

bfs가 실행되었다는 것은 'P'가 발견되었다는 뜻이므로 해당 위치 값을 담는 Point 객체를 담을 Queue를 선언한다.

 

그 이후에 해당 노드를 다시 방문하지 않아도 될 수 있게 방문 여부를 표기하고 

큐에 해당 노드를 담아준다.

=> 방문 여부를 확인해두지 않으면 상,하,좌,우를 확인하는 과정에서

시작노드에서 한번만 이동하고 거기서 또 시작 노드로 되돌아오고 또 시작 노드에서 이전 노드로 가고 하는 무한 반복이 일어나게 된다.

이 문제의 경우 거리에 대한 제한 조건이 있었기 때문에 무한 루프가 도는 문제가 생기지 않았지만

거리에 대한 조건이 없었다면 무한 루프에 빠지는 문제가 생길 수 있고 더욱이 정답 자체가 틀리게 된다.

 

이후에 큐에서 데큐를 진행하며 재귀적으로 호출하게 되는데 

문제에서 주어진 조건을 bfs를 진행하는 과정에서 걸어준다.

 

총 이동거리가 2 초과면 continue

시작 노드가 아닐 때(dist != 0) 현재 탐색하려고 하는 노드의 값이 P이면 탐색을 더 이상 진행할 필요가 없어지므로 완전히 탈출해서 answer 배열에 0 대입.

 

이제 해당 노드의 상,하,좌,우를 이동하게 정의해둔 행동을 실행시킨다.

그리고 노드를 이동하며 생기게 되는 예외값을 처리한다.

 

5X5 배열의 크기를 넘어가는 경우 continue

해당 노드를 이미 방문한 적이 있으면 continue

해당 노드의 값이 X라면 문제의 조건에 의해 지나갈 수 없는 곳이므로 continue

 

위 조건에 걸리지 않으면 단순히 현재 위치에서부터 방문할 수 있는 곳은 전부 방문한 것이므로 방문 여부 체크하고

해당 노드를 큐에 넣는다.

 

위 조건에 의해 다시 노드가 큐에 쌓이게 되므로 while문이 계속 돌아가게 된다.

큐에 남은 것이 아무것도 없을 때까지 데큐를 했음에도 false값이 리턴되지 않았다면, 즉 P에서 시작해서 맨해튼 거리 2 이내로 P를 발견하지 않았다면

 

너비 탐색 결과에 의해 해당 지원자는 거리두기를 지키고 있는 것으로 판단하고

true를 반환하게 된다.

 

    boolean bfs(String[] place, int row, int col) {
        boolean[][] visited = new boolean[5][5];

        Queue<Point> q = new LinkedList<>();
        visited[row][col] = true;
        q.add(new Point(row, col, 0));
        
        while (!q.isEmpty()) {
            Point curr = q.remove();
            
            if (curr.dist > 2) continue;
            if (curr.dist != 0 && place[curr.row].charAt(curr.col) == 'P') {
                return false;
            }
            
            for (int i = 0; i < 4; i++) {
                int newRow = curr.row + D[i][0];
                int newCol = curr.col + D[i][1];
                
                if (newRow < 0 || newRow > 4 || newCol < 0 || newCol > 4) continue;
                if (visited[newRow][newCol]) continue;
                if (place[newRow].charAt(newCol) == 'X') continue;
                visited[newRow][newCol] = true;
                q.add(new Point(newRow, newCol, curr.dist + 1));
            }
        }
        return true;
    }

 

 

다시 check 메서드로 되돌아와서 P를 찾는 과정을 거치게 되고 

P를 찾으면 bfs 실행 결과에 따른 boolean 반환.

이렇게 돌았음에도 false가 return 되지 않았다면 true를 반환한다.

 

    boolean check(String[] place) {
        
        for (int row = 0; row < 5; row++) {
            for (int col = 0; col < 5; col++) {
                if (place[row].charAt(col) == 'P') {
                    if (!bfs(place, row, col))
                        return false;
                }
            }
        }
        return true;
    }

 

다시 메인 메서드로 돌아와서 check 결과에 answer 배열을 채워주고 

3차 배열의 첫번째 2차 배열이 끝났으므로 그 다음 2차 배열에 대한 검증을 시작한다.

3차 배열에 대한 모든 검증이 끝났다면 검증 결과값을 담은 answer 배열을 반환하며 끝. 

    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        
        for (int i = 0; i < 5; i++) {
            if (check(places[i])) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }
        return answer;
    }

 

 

레퍼런스

https://youtu.be/jdUg2NYBAyM

 

https://sangdo913.tistory.com/183

[알고리즘 깨알 팁] BFS 짜는 법