문제 설명
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
예를 들어,
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] |
입출력 예 설명
입출력 예 #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 합니다.
제한시간 안내
- 정확성 테스트 : 10초
1. 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. ↩
💛 나의 풀이
from collections import deque
def isin(nx, ny) : # 인덱스 범위 확인
if 0 <= nx < 5 and 0 <= ny < 5 :
return True
return False
def bfs(place, i, j):
que=deque([[i, j, 0]])
visited=[[-1]*5 for i in range(5)]
visited[i][j]=0
while que :
a, b, d=que.popleft() # 행, 열, 거리
for dx, dy in [(0, 1), (0, -1), (-1, -0), (1, 0)] :
nx=a+dx
ny=b+dy
if isin(nx, ny) :
if visited[nx][ny] == -1:
visited[nx][ny]=1
if place[nx][ny] == "P" and d+1 <= 2 : # 거리두기 실패
return False
elif place[nx][ny] != "X" :
que.append([nx, ny, d+1])
return True
def solution(places):
answer = []
for place in places:
flag = True
for i in range(5):
for j in range(5):
if place[i][j] == "P":
if not bfs(place, i, j):
flag = False
break
if not flag: break
if not flag:
answer.append(0)
else:
answer.append(1)
return answer
bfs로 풀이
P를 찾으면 bfs를 호출해서 거리두기를 하고있는지 확인
가림막이 아니면 que에 담는다.
import java.util.*;
class Node{
int i, j, d;
Node(int i, int j, int d){
this.i=i;
this.j=j;
this.d=d;
}
}
class Solution {
public boolean valid(int nx, int ny){
if(-1 < nx && nx < 5 && -1 < ny && ny < 5){
return true;
}
return false;
}
public boolean bfs(int x, int y, String[] place){
Queue<Node> que=new LinkedList<>();
que.add(new Node(x, y, 0));
boolean[][] visited=new boolean[5][5];
visited[x][y]=true;
int[][] pos={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while(!que.isEmpty()){
Node node=que.poll();
for(int[] dxdy : pos){
int nx=dxdy[0]+node.i;
int ny=dxdy[1]+node.j;
if(!valid(nx, ny)) continue;
if(!visited[nx][ny]){
visited[nx][ny]=true;
if(place[nx].substring(ny, ny+1).equals("P") && node.d+1 <= 2){
return false;
}
if(!place[nx].substring(ny, ny+1).equals("X")){
que.add(new Node(nx, ny, node.d+1));
}
}
}
}
return true;
}
public int[] solution(String[][] places) {
ArrayList<Integer> answer = new ArrayList<>();
for(String[] place : places){
int flag=1;
for(int i=0; i<5; i++){
for(int j=0; j<5; j++){
if(place[i].substring(j, j+1).equals("P")){
if(!bfs(i, j, place)) {
flag = 0;
break;
}
}
}
if(flag != 1) break;
}
answer.add(flag);
}
return answer.stream().mapToInt(i->i).toArray();
}
}
자바로 구현한 bfs 풀이
문자열은 인덱스로 접근할 수 없어서 substirng으로 가져왔다.
멤버변수 행 i, 열 j, 거리 d를 가지는 객체를 que에 넣는다.
answer = [1] * 5
def dfs(place, idx, i, j, count, visited):
if count > 2: return
if place[i][j] == "P" and 0 < count <= 2:
answer[idx] = 0
return
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = i + dx, j + dy
if 0 <= nx < 5 and 0 <= ny < 5:
if not visited[nx][ny] and place[nx][ny] != "X":
visited[nx][ny] = 1
dfs(place, idx, nx, ny, count + 1, visited)
visited[nx][ny] = 0
def solution(places):
idx = 0
for place in places:
visited = [[0] * 5 for i in range(5)]
for i in range(5):
for j in range(5):
if place[i][j] == "P":
visited[i][j] = 1
dfs(place, idx, i, j, 0, visited)
visited[i][j] = 0
idx += 1
return answer
dfs로 구현했을 때 아래처럼 실패가 떴었는데 다른 사람이 자바로 구현한 풀이를 보고 해결~~
나는 visited로 거리 계산, 방문 처리를 동시에 했었다.
이게 문제인듯... return해서 처음 호출했던 시점으로 돌아가면서 값이 바뀔 수 있다.
외부의 리스트 answer에 0또는 1을 저장한다.
dfs(대기실 문자열 리스트, 대기실 번호, 문자열 행 인덱스, 문자열 열 인덱스, 방문기록)이다.
파라미터가 많아서 보기 쉽게 적어봄
# 실패
def dfs(place, i, j, visited):
for dx, dy in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
nx = i + dx
ny = j + dy
if 0 > nx or nx >= 5 or 0 > ny or ny >= 5: continue # 인덱스 초과 에러 방지
if not visited[nx][ny] :
visited[nx][ny] = visited[i][j] + 1
if visited[nx][ny] <= 2 and place[nx][ny] == "P":
return False
if place[nx][ny] != "X" and visited[nx][ny] == 0 :
dfs(place, nx, ny, visited)
return True
def solution(places):
answer = []
for place in places:
flag = True
for i in range(5):
for j in range(5):
if place[i][j] == "P":
visited = [[0] * 5 for i in range(5)]
visited[i][j] = 1
if not dfs(place, i, j, visited):
flag = False
break
if not flag: break
if not flag:
answer.append(0)
else:
answer.append(1)
return answer
79.1점으로 실패(3, 5, 8, 11, 13, 16)
🐱 다른 사람 풀이
# https://velog.io/@study-dev347/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0-%ED%99%95%EC%9D%B8%ED%95%98%EA%B8%B0
from collections import deque
d=((0, 1), (1, 0), (-1, 0), (0, -1))
SIZE=5
def make_maps(place) :
arr=[]
men=[]
for i, string in enumerate(place) :
for j, ch in enumerate(string) :
if ch == 'P' : men.append((i, j))
arr.append(list(string))
return arr, men
# 범위 체크
def isin(y, x) :
if -1 < y < SIZE and -1 < x < SIZE : return True
return False
def bfs(arr, sy, sx) :
q=deque()
q.append((sy, sx))
table=[[-1 for _ in range(SIZE)] for _ in range(SIZE)]
table[sy][sx]=0
while q :
y, x=q.popleft()
for dy, dx in d :
ny=y+dy
nx=x+dx
if not isin(ny, nx) : continue # 범위 체크
if arr[ny][nx] != 'X' and table[ny][nx] == -1 :
table[ny][nx]=table[y][x]+1
q.append((ny, nx))
return table
def solution(places) :
answer=[]
for place in places :
arr, men=make_maps(place)
ok=True
for man in men :
table=bfs(arr, man[0], man[1])
for other_man in men :
if man != other_man :
y=other_man[0]
x=other_man[1]
if -1 < table[y][x] <= 2 :
ok=False
break
if not ok : break
if ok : answer.append(1)
else : answer.append(0)
return answer
make_maps 함수에서는 places의 각 문자열을 문자로 쪼개 arr에 담고, men에 P의 좌표를 담는다.
bfs 함수로 거리두기를 지켰는지 확인한다.
table 리스트에 어떤 P와 근처의 P 좌표와의 맨해튼 거리를 기록한다.
맨해튼 거리가 2인 위치를 발견하면 ok=False 후 break한다.
ok에 따라 1 또는 0을 리스트에 추가한다.
# https://bladejun.tistory.com/162
from collections import deque
def bfs(p, idx) :
q=deque([idx])
visited=[[False]*5 for _ in range(5)]
dic={0:[0, -1], 1:[-1, 0], 2:[0, 1], 3:[1, 0]}
while q:
x, y, d=q.popleft()
visited[x][y]=True
for i in range(4) :
nx=x+dic[i][0]
ny=y+dic[i][1]
nd=d+1
if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny] :
visited[nx][ny]=True
if p[nx][ny] == 'P' :
if nd <= 2 :
return False
elif p[nx][ny] == '0' :
if nd == 1 :
q.append([nx, ny, nd])
return True
def solution(places) :
answer=[]
for p in places :
flag=1
for i in range(5) :
for j in range(5) :
if p[i][j] == 'P' :
result=bfs(p, [i, j, 0])
if not result :
flag=0
answer.append(flag)
return answer
위에보다 좀더 간단한 bfs 풀이
"P"를 찾으면 bfs를 호출한다.
bfs에서 맨해튼 거리가 2이하인지 판단하고 있다.
# https://soniacomp.medium.com/%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0-%ED%99%95%EC%9D%B8%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-d663b2198170
def solution(places) :
answer=[]
size=5
def valid(r, c) :
return -1 < r < size and -1 < c < size
def check(x, y, place) :
dist=[(1, 0), (0, 1), (-1, 0), (0, -1)]
for dx, dy in dist :
nx, ny=x+dx, y+dy
if valid(nx, ny) and place[nx][ny] == "P" :
return False
dist=[(-1, -1), (-1, 1), (1, -1), (1, 1)]
for dx, dy in dist :
nx, ny=x+dx, y+dy
if valid(nx, ny) and place[nx][ny] == "P" and (place[x][ny] != "X" or place[nx][y] != "X") :
return False
dist=[(2, 0), (0, 2), (-2, 0), (0, -2)]
for dx, dy in dist :
nx, ny=x+dx, y+dy
if valid(nx, ny) and place[nx][ny] == "P" and place[x+dx//2][y+dy//2] != "X" :
return False
return True
for place in places :
flag=False
for r, c in [(i, j) for i in range(5) for j in range(5)] :
if place[r][c] == "P" :
result=check(r, c, place)
if not result :
answer.append(0)
flag=True
break
if not flag :
answer.append(1)
return answer
for문으로 문제의 조건에 맞게 구현한 코드
거리가 2이하인 좌표 모두 확인한다.
초록색 좌표(-1, -1)가 P인 경우 (0, -1), (-1, 0)이 X가 되어야 거리두기가 된다.
아래 그림 조건을 확인하는 것이다.
주황색 좌표(0, -2)가 P인 경우 (0, -1)이 X가 되어야 거리두기가 된다.
아래의 조건에 해당함
if isin(nx, ny) and place[nx][ny] == "P" and place[(i+nx)//2][(j+ny)//2] != "X" :
return False나는 이게 더 직관적인 것 같다.
아니면 파란블럭이
nx, ny=i+dx, j+dy,
place[nx][ny]이므로 place[i+dx][j+dy]랑 같다.
파란블럭의 dx, dy는 주황블럭의 dx, dy의 절반이니까
place[i+dx//2][j+dy//2]가 나온다.
class Solution {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static boolean[][] visit;
static int[] answer;
public void dfs(int num, int x, int y, int count, String[] places){
if (count > 2) return;
if (count > 0 && count <= 2 && places[x].charAt(y) == 'P'){
//2칸 범위내에 다른 응시자가 있을 경우 거리두기 미준수로 0처리
answer[num] = 0;
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
//배열 범위 밖으로 초과하는지 여부 검사, 파티션으로 분리되어 있는 경우 상관 없음.
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && places[nx].charAt(ny) != 'X') {
if (visit[nx][ny]) continue; //이미 방문한 곳일 경우 생략
visit[nx][ny] = true;
dfs(num, nx, ny, count + 1, places);
visit[nx][ny] = false;
}
}
}
public int[] solution(String[][] places) {
answer = new int[places.length];
for (int i = 0; i < places.length; i++) {
answer[i] = 1;
}
for (int i = 0; i < places.length; i++) {
visit = new boolean[5][5];
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
if (places[i][j].charAt(k) == 'P'){
visit[j][k] = true;
dfs(i, j, k, 0, places[i]);
visit[j][k] = false;
}
}
}
}
return answer;
}
}
자바로 구현한 dfs 풀이
거리를 계산할 때는 dfs보다 bfs로 구현하는 게 편하긴 하다
그래도 알아두면 좋으니까!!
문제 출처 👉 프로그래머스
반응형
'coding test' 카테고리의 다른 글
| [파이썬] [1차] 프렌즈4블록 (0) | 2021.08.20 |
|---|---|
| [파이썬] 후보키 (0) | 2021.08.16 |
| [파이썬, Java] 숫자 문자열과 영단어 (0) | 2021.07.15 |
| [파이썬, Java] 가장 큰 수 (0) | 2021.07.08 |
| [Java] 2003. 수들의 합 2 (0) | 2021.07.05 |