오늘 풀어볼 문제는
프로그래머스의 '거리두기 확인하기'로,
2021 카카오 채용연계형 인턴십에 나왔던 문제입니다.
위드코로나로 전환되며
이제는 거리두기가 벌써 먼 과거가 되었지만
문제를 풀어보며 실생활적인 발상, 궁금증을 알고리즘으로 풀어보도록 하겠습니다.
🪑 거리두기 확인하기
2021 카카오 채용연계형 인턴십
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
대기실은 5개이며, 각 대기실은 5x5 크기입니다.
거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
예를 들어, 위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다.
위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다.
위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를 지키지 않은 것입니다.
(두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. )
응시자가 앉아있는 자리(P)를 의미합니다.
빈 테이블(O)을 의미합니다.
파티션(X)을 의미합니다.
❓ question
5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다.
자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다.
각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
❗ 제한사항
- places의 행 길이(대기실 개수) = 5
- places의 각 행은 하나의 대기실 구조를 나타냅니다.
- places의 열 길이(대기실 세로 길이) = 5
- places의 원소는 P,O,X로 이루어진 문자열입니다.
- places 원소의 길이(대기실 가로 길이) = 5
- P는 응시자가 앉아있는 자���를 의미합니다.
- O는 빈 테이블을 의미합니다.
- X는 파티션을 의미합니다.
- 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
❕ return 값 형식
1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.
입출력 예
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]
{{"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
첫 번째 대기실
No. 0 1 2 3 4
0 P O O O P
1 O X X O X
2 O P X P X
3 O O X O X
4 P O X X P
모든 응시자가 거리두기를 지키고 있습니다.
두 번째 대기실
No. 0 1 2 3 4
0 P O O P X
1 O X P X P
2 P X X X O
3 O X X X O
4 O O O P P
(0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
(1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
(4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
세 번째 대기실
No. 0 1 2 3 4
0 P X O P X
1 O X O X P
2 O X P O X
3 O X X O P
4 P X P O X
모든 응시자가 거리두기를 지키고 있습니다.
네 번째 대기실
No. 0 1 2 3 4
0 O O O X X
1 X O O O X
2 O O O X X
3 O X O O X
4 O O O O O
대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.
다섯 번째 대기실
No. 0 1 2 3 4
0 P X P X P
1 X P X P X
2 P X P X P
3 X P X P X
4 P X P X P
모든 응시자가 거리두기를 지키고 있습니다.
▶ 두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.
class Solution {
public int[] solution(String[][] places) {
int[] answer = {};
return answer;
}
}이 문제는 5x5 크기의 대기실에서 응시자들이 거리두기를 잘 지키고 있는지 확인하는 문제입니다.
거리두기를 위한 조건은 맨해튼 거리가 2 이하로 앉지 말아야 하며, 파티션으로 막혀 있는 경우에는 허용됩니다.
이러한 문제를 해결하는 데에는 탐색 알고리즘을 이용할 수 있을 거 같습니다.
너비 우선 탐색(BFS) or 깊이 우선 탐색(DFS) 알고리즘
둘 중 어떤 것이 더 적합한지 판단하기 위해서는 문제의 특성을 4가지 각도로 고려해보겠습니다.
접근하기
최단 거리 탐색:
이 문제에서는 응시자들 사이의 거리를 계산하여 거리두기를 지켰는지 확인해야 합니다.
BFS는 너비 우선 탐색이므로 시작점으로부터 레벨별로 탐색을 진행합니다.
이는 최단 거리를 먼저 찾아내는 특성을 가지고 있습니다. 따라서 BFS를 사용하면 최단 거리를 더 효율적으로 찾을 수 있습니다.
=> bfs는 이동할 때 최단거리로 이동
탐색 범위 제한:
거리두기를 확인할 때, 맨해튼 거리가 2 이하인 응시자만을 고려해야 합니다.
BFS는 시작점에서부터 주어진 조건에 맞는 노드만을 탐색하므로, 맨해튼 거리가 2 이하인 응시자들만을 고려할 수 있습니다.
반면에 DFS는 깊이 우선 탐색이기 때문에 시작점에서부터 모든 경로를 탐색하게 됩니다.
=> 조건에 맞는 노드들만을 탐색
공간 효율성:
대기실의 크기가 고정되어 있고, 응시자들 사이의 맨해튼 거리가 2 이하인 경우만을 고려해야 합니다.
BFS는 너비 우선 탐색이므로 한 번에 한 레벨씩 탐색하면서 공간을 효율적으로 사용할 수 있습니다.
반면에 DFS는 깊이 우선 탐색이므로 재귀 호출을 사용하면서 스택에 깊게 들어가는 경우가 발생할 수 있습니다.
=> 쓸데 없이 깊게 들어갈 필요 없다
종료 조건:
BFS는 종료 조건이 명확하게 설정되어 있습니다.
시작점에서부터 BFS를 수행하다가 최단 거리를 찾았을 때 탐색을 종료하면 됩니다.
하지만 DFS는 모든 경로를 탐색해야 하므로 종료 조건을 설정하기가 어려울 수 있습니다.
=> 종료조건 설정에 유리하다
따라서 이 문제에서는 거리두기를 확인하기 위해 BFS가 더 적합합니다.
sudo 코드를 작성하면 다음과 같습니다.
문제 풀이
💡 sudo code
- 대기실 생성 char[][] place 배열에 담아줍니다.
- 대기실 생성시 방문여부 배열을 초기화합니다.
- 대기실을 순회하며 사람(P)인 경우 bfs 함수를 호출하여 근방을 탐색합니다.
3-0. 시작점을 큐에 넣고, 해당 시작점을 방문처리해준다.
★ 큐가 비어있지 않는 동안 3-1부터 3-4까지 반복한다
3-1. 요소 추출 및 종료조건 확인 : 큐에서 요소를 꺼내고, 해당 요소가 맨해튼거리(depth) 2를 초과하였는지, 사람(P)인지 확인한다.
해당하는 경우 맨해튼거리 초과는 무시, 사람은 false를 리턴한다.
3-2. 조건에 맞는 노드 탐색 : 위의 조건에 해당하지 않는 경우 상하좌우 탐색을 한다.
3-2. 레벨별 탐색 : 배열접근 범위에 들어가고, 파티션(X)이 아니라서 접근할 수 있고, 아직 방문할 수 있는 요소를 큐에 추가한다.
3-3. 해당 요소를 방문처리한다.- 3번에서 호출한 bfs에서 한 번이라도 false가 나면 결과값을 false로 update하고, 현재 대기실 탐색을 빠져나온다.
- 최종적으로 현재 대기실에 대한 결과값을 바탕으로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.
💻 code
import java.util.*;
class Solution {
public Queue<int[]> queue;
public boolean[][] visited;
public int[] dx = {-1, 1, 0, 0};
public int[] dy = {0, 0, -1, 1};
public int[] solution(String[][] places) {
int[] answer = new int[5];
for(int k=0; k<places.length; k++) {
// 대기실 선언
char[][] place = new char[5][5];
// 1. 대기실 생성 char[][] place 배열에 담아줍니다.
for(int j=0; j<5; j++) {
place[j] = places[k][j].toCharArray();
}
// 2. 대기실 생성시 방문여부 배열을 초기화합니다.
visited = new boolean[5][5];
boolean result = true;
// 3. 대기실을 순회하며 사람(P)인 경우 bfs 함수를 호출하여 근방을 탐색합니다.
for(int i=0; i<place.length; i++) {
for(int j=0; j<place[i].length; j++) {
if(place[i][j] == 'P') {
// 거리두기 결과값을 넣어준다
if((!bfs(place, i, j, 0))) {
result = false;
break;
}
}
}
}
answer[k] = !result ? 0 : 1;
}
return answer;
}
public boolean bfs(char[][] place, int x, int y, int dep) {
queue = new LinkedList<>();
// 3-0. 시작점을 큐에 넣고, 해당 시작점을 방문처리해준다.
queue.offer(new int[] {x, y, dep});
visited[x][y] = true;
// 큐가 비어있지 않는 동안 3-1부터 3-4까지 반복한다
while(!queue.isEmpty()) {
int[] arr = queue.poll();
int row = arr[0];
int col = arr[1];
int depth = arr[2];
// 3-1. 요소 추출 및 종료조건 확인 : 큐에서 요소를 꺼내고, 해당 요소가 맨해튼거리(depth) 2를 초과하였는지, 사람(P)인지 확인한다. 해당하는 경우 맨해튼거리 초과는 무시, 사람은 false를 리턴한다.
if(depth > 2) continue;
if(depth != 0 && place[row][col] == 'P') {
return false;
}
// 3-2. 조건에 맞는 노드 탐색 : 위의 조건에 해당하지 않는 경우 상하좌우 탐색을 한다.
for(int i=0; i<4; i++) {
int newRow = row + dx[i];
int newCol = col + dy[i];
// 3-2. 레벨별 탐색 : 배열접근 범위에 들어가고, 파티션(X)이 아니라서 접근할 수 있고, 아직 방문할 수 있는 요소를 큐에 추가한다.
if(newRow >= 0 && newRow < 5 && newCol >= 0 && newCol < 5 &&
place[newRow][newCol] != 'X' &&
!visited[newRow][newCol]) {
queue.offer(new int[] {newRow, newCol, depth+1});
visited[newRow][newCol] = true; // 3-3. 해당 요소를 방문처리한다.
}
}
}
return true;
}
public static void main(String[] args) {
Solution sol = new Solution();
// String[][] places = {{"OOPOO", "OPOOO", "OOOOO", "OOOOO", "OOOOO"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}};
String[][] places = {{"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"}};
int[] result = sol.solution(places);
for(int i:result) {
System.out.print(i + " ");
}
}
}개인적으로 해당 문제에서 깨달음을 얻음 부분은 두 가지입니다.
1) 단일한 시작점이 주어졌던 bfs 문제에서 벗어나, bfs를 여러 번 호출할 수 있었다는 점
2) 상하좌우를 접근할 때 배열을 이용하면 편하다는 점
알고리즘을 공부하다보면 항상 틀을 깨고, 다시 넓혀가는 기분이 듭니다.
다음 풀이로 다시 돌아오겠습니다.
더 좋은 풀이가 있다면 언제든 피드백 부탁드립니다. 감사합니다 :)
