2021 카카오 채용연계형 인턴십 Lv2 거리두기 확인하기 [Java]

2021 카카오 채용연계형 인턴십 Lv2 거리두기 확인하기

1. 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/81302

2. 문제 해설

카카오 2021 채용연계형 인턴십 코딩테스트의 2번 문제이다.
맨해튼 거리가 2이하면 안된다는 의미는 bfs를 동서남북으로 돌았을 때 깊이 2 이하로는 참가자가 있으면 안된다는 의미이다.
각 대기실을 돌면서 참가자를 만나면 bfs를 돌아 거리두기 확인 여부를 검사하는 방식으로 풀고자 했다.

일단 큰 틀을 먼저 잡기 위해 int 배열을 반환하는 solution 메서드를 먼저 구현했다.
5가지 대기실의 거리두기를 지켰는지 여부를 담을 answer 배열을 만들어준다. 그리고 3중 for문을 돌아야하는데, i는 대기실의 갯수, j와 k는 각 대기실의 행과 열을 의미한다. 각 대기실마다 check 변수를 만들어주어 거리두기를 지켰는지 안지켰는지를 담았다.
한 대기실 내에서 행과 열을 다 돌면서 참가자를 만나면 BFS 메서드를 실행해줄 것이다. BFS 메서드는 참이면 거리두기를 지킨 것이고 거짓이면 거리두기를 지키지 않은 것을 의미한다. 한명의 참가자라도 거리두기를 지키지 않으면 거리두기를 지키지 않은 것이므로 BFS 메서드가 거짓이면 check를 false로 바꿔주고 j, k for문을 탈출해준다. check가 true면 answer[i]에 1을 false면 0을 담아주면 된다.

그렇다면, 이제 BFS 메서드를 구현해야한다. 큐에 참가자의 위치를 쉽게 담기 위해 참가자의 위치를 담는 Point 클래스를 만든다. BFS 메서드는 참가자의 위치와 대기실의 정보를 매개변수로 받아야한다. 이제 bfs를 돌 것인데 돌면서 만나는 칸이 무엇이냐에 따라 결과가 달라진다.

1. 맨해튼 거리 1인 경우 (bfs 깊이 1)
- P 인 경우 -> 거리두기를 지키지 않은 경우
- O 인 경우 -> 한번 더 bfs를 해보아야 함 -> 큐에 넣는다
- X 인 경우 -> 거리두기를 지킴

맨해튼 거리가 1인 경우는 bfs를 동서남북으로 돌면서 만나는 칸이 무엇이냐에 따라 위와 같이 갈린다. 참가자를 만나면 무조건 거리두기를 어긴 것이고, 파티션을 만나면 어떤 경우에도 거리두기를 지키게 된다. 빈 테이블이 있으면 거기서 한번 더 동서남북으로 bfs를 돌아봐야한다. 그래서 빈 테이블을 만나면 그 위치를 큐에 넣는다.

2. 맨해튼 거리 2인 경우 (bfs 깊이 2)
- P 인 경우 -> 거리두기를 지키지 않은 경우
- O 인 경우 -> 거리두기를 지킴
- X 인 경우 -> 거리두기를 지킴

맨해튼 거리가 1인 경우(bfs 깊이 1)에서 빈 테이블을 만나면 bfs를 한번 더 돌아서 살펴봐야한다. 그 경우가 맨해튼 거리가 2인 경우(bfs 깊이 2)인데, 그 상황에서 참가자를 만나면 거리두기를 어기게 된 것이다. 빈 테이블을 만나면 이번에는 한번 더 돌면서 살펴볼 필요가 없다. 현재 빈테이블을 만났다고 하면 대강 P O O 이런 상황인데 여기서 한칸 더 가면 맨해튼 거리가 2보다 커져서 자연스레 거리두기를 지킨 경우가 된다.

위 내용을 구현한 코드를 아래에서 확인해보자.

3. 코드 보기

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    class Point {
        int r;
        int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    boolean BFS(int r, int c, String[] str) {
        Queue<Point> q = new LinkedList<Point>();
        boolean[][] vis = new boolean[5][5];
        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};

        q.add(new Point(r, c));
        vis[r][c] = true;

        while (!q.isEmpty()) {
            Point cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];

                if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5 || vis[nr][nc]) {
                    continue;
                }

                int dis = Math.abs(r - nr) + Math.abs(c - nc);

                if (str[nr].charAt(nc) == 'P' && dis <= 2) {
                    return false;
                }

                if (str[nr].charAt(nc) == 'O' && dis < 2) {
                    q.add(new Point(nr, nc));
                    vis[nr][nc] = true;
                }
            }
        }

        return true;
    }

    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        for (int i = 0; i < 5; i++) {
            boolean check = true;

            for (int j = 0; j < 5; j++) {
                if (!check) {
                    break;
                }

                for (int k = 0; k < 5; k++) {
                    if (!check) {
                        break;
                    }

                    if (places[i][j].charAt(k) == 'P') {
                        if (!BFS(j, k, places[i])) {
                            check = false;
                        }
                    }
                }
            }

            if (check) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }

        return answer;
    }
}