프로그래머스 | Level 2 | 거리두기 확인하기
Programmers | Level 2 | 거리두기 확인하기
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Breadth-First Search
Description
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
- 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
- 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
- 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
예를 들어,
5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
Constraints
places의 행 길이(대기실 개수) = 5places의 각 행은 하나의 대기실 구조를 나타냅니다.
places의 열 길이(대기실 세로 길이) = 5places의 원소는P,O,X로 이루어진 문자열입니다.places원소의 길이(대기실 가로 길이) = 5P는 응시자가 앉아있는 자리를 의미합니다.O는 빈 테이블을 의미합니다.X는 파티션을 의미합니다.
- 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
return값 형식- 1차원 정수 배열에 5개의 원소를 담아서
return합니다. places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.- 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.
- 1차원 정수 배열에 5개의 원소를 담아서
Examples
| places | result |
|---|---|
[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] | [1, 0, 1, 1, 1] |
Solutions
Code
import java.util.*;
class Solution {
// 상하좌우로 이동하기 위한 델타 배열
private static final int[] dx = {0, 1, 0, -1};
private static final int[] dy = {1, 0, -1, 0};
public int[] solution(String[][] places) {
int[] result = new int[places.length];
int rows = 5, cols = 5;
for (int room = 0; room < places.length; room++) {
Deque<int[]> people = new ArrayDeque<>(); // 응시자 위치 기록
int[][] grid = new int[rows][cols]; // 대기실 상태 배열
String[] place = places[room];
// 대기실 초기화 및 응시자 위치 확인
for (int i = 0; i < rows; i++) {
String line = place[i];
for (int j = 0; j < cols; j++) {
if (line.charAt(j) == 'P') {
people.offer(new int[]{i, j}); // 응시자 위치 저장
grid[i][j] = 2; // 응시자 위치 표시
} else if (line.charAt(j) == 'X') {
grid[i][j] = 1; // 파티션 위치 표시
}
}
}
result[room] = bfs(people, grid, rows, cols); // BFS로 거리두기 준수 여부 확인
}
return result;
}
private int bfs(Deque<int[]> people, int[][] grid, int rows, int cols) {
while (!people.isEmpty()) {
Deque<int[]> queue = new ArrayDeque<>();
boolean[][] marked = new boolean[rows][cols]; // 방문 여부 기록
int[] person = people.poll();
int sx = person[0], sy = person[1];
queue.offer(new int[]{sx, sy, 0}); // 시작점(응시자 위치)에서 탐색 시작
marked[sx][sy] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
for (int i = 0; i < 4; i++) { // 상하좌우 4방향 탐색
int nx = dx[i] + current[0];
int ny = dy[i] + current[1];
int ns = current[2] + 1; // 이동 거리 증가
if (isOutbounds(nx, ny, rows, cols) || marked[nx][ny] || grid[nx][ny] == 1) continue; // 범위 밖 또는 파티션이거나 이미 방문한 위치일 경우 무시
if (grid[nx][ny] == 2 && ns < 3) return 0; // 다른 응시자와 맨해튼 거리 2 이내에 위치 시 거리두기 위반
queue.offer(new int[]{nx, ny, ns}); // 다음 탐색을 위해 큐에 추가
marked[nx][ny] = true; // 방문 처리
}
}
}
return 1; // 거리두기 지켰을 경우
}
private boolean isOutbounds(int nx, int ny, int rows, int cols) {
return nx < 0 || ny < 0 || nx >= rows || ny >= cols; // 좌표가 대기실 범위를 벗어나는지 확인
}
}
Approaches
이 문제는 BFS(너비 우선 탐색)를 사용해 대기실에서 응시자들이 거리두기를 준수하는지 확인하는 방식으로 해결할 수 있습니다. 각 응시자는 상하좌우로 맨해튼 거리 2 이내에 다른 응시자가 있으면 거리두기를 위반하게 됩니다. 단, 중간에 파티션이 있을 경우 거리두기를 지킨 것으로 간주합니다.
1. 문제 분석
거리두기 확인하기 문제는 복잡해 보이지만, 핵심은 파티션을 하나의 벽처럼 간주하고 사람들 간의 최단 거리를 계산하는 데 있습니다. 각 사람의 위치에서 다른 사람과의 거리를 탐색하면서, 거리가 맨해튼 거리 2 이하인 경우를 확인해야 합니다.
모든 사람마다 BFS를 통해 상하좌우로 이동하면서 다른 사람과의 거리를 계산합니다. 거리가 2 이하인 다른 사람을 발견하는 즉시 탐색을 종료하고, 해당 대기실은 거리두기 규칙을 위반한 것으로 처리합니다.
2. 접근 방식
거리두기 규칙을 확인하기 위한 방법으로 BFS 알고리즘을 사용합니다. 탐색은 한 응시자가 다른 응시자와의 거리가 2 이하인지, 그 사이에 파티션이 있는지를 확인하는 방식으로 진행됩니다.
- 게임판 초기화 및 응시자 위치 찾기: 먼저, 대기실을 2차원 배열로 변환하고, 각 응시자 위치를 저장합니다. 이때 "P"는 응시자 위치로, "X"는 파티션 위치로 기록됩니다.
- BFS 탐색을 위한 큐 초기화: 각 응시자의 위치에서 BFS 탐색을 시작하여 상하좌우로 이동합니다. 이동할 때마다 빈 테이블을 지나 다른 응시자에게 도달할 수 있는지, 그 사이에 파티션이 있는지를 확인합니다.
- 거리 계산 및 거리두기 규칙 확인: BFS 탐색을 통해 응시자 간의 거리가 2 이하인 경우, 파티션이 없는지 확인하여 규칙 위반 여부를 결정합니다.
- 탐색 종료 및 결과 반환: 각 대기실에 대해 탐색을 완료한 후, 거리두기 규칙을 지켰는지 여부에 따라 1 또는 0을 반환합니다.
3. 대기실 초기화 및 BFS 탐색 준비
대기실 상태를 2차원 배열로 변환하고, 각 응시자와 파티션의 위치를 저장합니다. 응시자는 P, 파티션은 X로 표현되며, 빈 테이블은 O로 표현됩니다. 탐색의 시작점이 되는 응시자의 위치는 큐에 저장하여 관리하고, 이후 거리 계산에서 장애물로 간주될 파티션의 위치는 별도로 기록합니다. 이 단계는 탐색을 위한 필수적인 초기 설정을 다루며, 이후 각 응시자와 다른 응시자 간의 거리를 계산하기 위한 준비 과정입니다.
int rows = 5;
int cols = 5;
Deque<int[]> people = new ArrayDeque<>(); // 응시자 위치를 저장할 큐
int[][] grid = new int[rows][cols]; // 대기실 상태 배열
// 대기실 초기화
for (int i = 0; i < rows; i++) {
String line = place[i];
for (int j = 0; j < cols; j++) {
if (line.charAt(j) == 'P') {
people.offer(new int[]{i, j}); // 응시자 위치 저장
grid[i][j] = 2; // 응시자 위치 표시
} else if (line.charAt(j) == 'X') {
grid[i][j] = 1; // 파티션 위치 표시
}
}
}
4. BFS 탐색 및 거리두기 규칙 확인
BFS 탐색을 통해 각 응시자의 위치에서 다른 응시자까지의 거리를 계산합니다. 이 과정에서 파티션은 벽으로 간주되어 해당 경로를 우회하게 되며, 결국 두 응시자 간에 파티션이 있더라도 맨해튼 거리 기준으로 거리를 측정할 수 있습니다.
탐색의 목표는 각 응시자의 위치에서 다른 응시자와의 거리가 2 이하인지 확인하는 것입니다. BFS는 최단 경로 탐색에 적합하기 때문에, 탐색 과정에서 파티션을 우회하며 정확하게 거리를 계산할 수 있습니다. 만약 거리가 2 이하인 경우, 규칙을 위반한 것으로 처리합니다.
탐색 흐름은 다음과 같습니다:
- 초기화: 각 응시자의 위치에서 BFS 탐색을 시작합니다. 큐에는 해당 응시자의 좌표와 현재까지의 이동 거리를 저장하며, 탐색이 진행됨에 따라 큐에서 응시자의 위치를 하나씩 꺼내면서 탐색을 이어갑니다.
- 4방향 탐색: 상하좌우 네 방향으로 이동하며, 파티션은 벽처럼 간주되어 경로를 차단합니다. 파티션이 있으면 해당 경로로 이동하지 않고 다른 방향을 탐색합니다.
- 거리 계산: 응시자 간의 거리가 2 이하인지 계산하며, 이때 파티션을 우회한 거리가 2 이하이면 규칙 위반으로 처리합니다.
- 즉시 종료: 만약 규칙을 위반한 응시자가 발견되면 즉시 탐색을 종료하고
0을 반환하여 해당 대기실이 규칙을 위반했음을 나타냅니다. - 탐색 완료 후 규칙 준수 확인: 탐색이 종료된 후에도 규칙 위반이 없으면
1을 반환하여 대기실이 규칙을 준수했음을 나타냅니다.
private int bfs(Deque<int[]> people, int[][] grid, int rows, int cols) {
// 응시자 목록에서 순차적으로 꺼내면서 다른 응시자와의 최단 거리 계산
while (!people.isEmpty()) {
Deque<int[]> queue = new ArrayDeque<>();
boolean[][] marked = new boolean[rows][cols]; // 방문 여부 기록
int[] person = people.poll(); // 탐색 시작 위치
int sx = person[0];
int sy = person[1];
queue.offer(new int[]{sx, sy, 0}); // 응시자 위치에서 탐색 시작
marked[sx][sy] = true; // 시작 위치 마킹
while (!queue.isEmpty()) {
int[] current = queue.poll();
for (int i = 0; i < 4; i++) { // 상하좌우 4방향 탐색
int nx = dx[i] + current[0];
int ny = dy[i] + current[1];
int ns = current[2] + 1; // 이동 거리 증가
// 범위를 벗어나거나, 이미 방문했거나, 파티션인 경우 탐색 제외
if (isOutbounds(nx, ny, rows, cols) || marked[nx][ny] || grid[nx][ny] == 1) continue;
// 거리 2 이내에 다른 응시자가 있으면 규칙 위반
if (grid[nx][ny] == 2 && ns < 3) return 0;
queue.offer(new int[]{nx, ny, ns});
marked[nx][ny] = true; // 방문 처리
}
}
}
return 1; // 규칙을 준수한 경우 1 반환
}
이 탐색 과정에서는 응시자 사이에 파티션이 있으면 해당 경로를 우회하여 탐색합니다. 이를 통해 응시자 간의 최단 거리를 계산하게 되며, 두 응시자 간의 거리가 2 이하이면 규칙을 위반한 것으로 간주하고 탐색을 즉시 종료합니다. 반면, 모든 응시자를 탐색하는 동안 규칙을 위반한 경우가 발견되지 않으면 해당 대기실은 거리두기 규칙을 준수한 것으로 처리됩니다.
5. 최종 결과 도출
모든 대기실에 대해 응시자를 탐색한 후, BFS 탐색을 통해 거리두기 규칙을 준수했는지 여부를 확인합니다. 각 대기실에서 거리두기를 지킨 경우 1을, 규칙을 위반한 경우 0을 반환합니다. 모든 대기실에 대한 결과를 배열에 저장한 후 최종적으로 그 결과를 반환합니다.
for (int room = 0; room < places.length; room++) {
...
// 각 대기실의 BFS 탐색 결과 저장
result[room] = bfs(people, grid, rows, cols);
}
// 최종 결과 반환
return result;
Complexity
- ⏳ TC: O(n * m)
- 💾 SC: O(n * m)
각 대기실은 m x m 크기의 배열로 주어지며, BFS 탐색을 통해 응시자 간의 거리를 확인합니다. 모든 응시자를 탐색해야 하므로 한 대기실에서 O(m * m)의 시간이 소요되며, 이를 n개의 대기실에 대해 반복하므로 총 시간 복잡도는 O(n * m)입니다. 공간 복잡도는 대기실의 상태와 방문 여부를 기록하기 위해 n x m 크기의 배열을 사용하고, 큐(Queue)를 이용해 응시자 위치를 저장하기 때문에 공간 복잡도는 O(n * m)입니다.
- Algorithm
- BFS