[python] programmers - 거리두기 확인하기

programmers - 거리두기 확인하기

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

프로그래머스

자세한 문제설명은 위의 링크를 참조하세요.

 

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

문제 풀이

이 문제는 예시를 통해 접근하는게 훨씬 쉽습니다. 응시자(P)들끼리 거리두기를 지키고 있는지 확인하는 문제입니다.

아래 예시를 살펴보면

2,1에 위치한 응시자와 2,3에 위치한 응시자는 맨해튼거리가 2지만, 그 사이에 파티션(X)가 존재합니다. 따라서 거리두기를 지키는 경우가 됩니다.

즉 문제에서 거리두기를 지키지 않는지 확인하기 위해서는 아래의 조건을 확인해야합니다.

 

맨해튼 거리가 2 이하이면서 두 응시자 사이를 파티션이 가로막지 않고 있는가?

 

위 조건을 완전탐색으로 검사하면 문제를 해결할 수 있을 것이라고 생각이 들었습니다.

하지만 좀 더 생각해야 할 부분이 남았는데 파티션의 위치입니다.

 

기준 응시자 P1 과 비교 응시자 P2가 있을때, 파티션이 어떤 위치에 존재해야 두 응시자를 가로막는걸까?  에 대한 답을 찾아야합니다.

 

몇 가지 예시를 통해 확인해보겠습니다.

기준 응시자 P1(0,3) 과 비교 응시자 P2(1,2)를 살펴봅시다. 맨해튼거리가 2 이므로 파티션의 위치를 체크해야하는데

0,2의 위치에 파티션이 존재하지 않으므로, 거리두기를 지키지 않고 있습니다.

 

P1의 x,y 좌표를 dx,dy라 하고 P2는 nx,ny라 설정했을때

 

cx = nx - dx = 1

cy = ny - dy = -1 

 

따라서 기준 응시자 P1의 좌표에서 cx 만큼 이동한 위치 ( dx+cx, dy) 와

cy만큼 이동한위치 (dx, dy+cy) 에 파티션이 존재해야 거리두기를 지킬 수 있는 것입니다.

 

위의 예시에서는 맨해튼 거리 2가 x,y 좌표에서 각각 1씩 차이로 인해 만들어졌는데 

첫번째 예시의 dx,dy(2,1)과 nx,ny(2,3)의 경우에는 y좌표만으로 맨해튼거리가 2가 됐습니다.

 

이 경우는 조금 다르게 생각해주어야하는 것이 

 

cx = nx - dx = 0

cy = ny - dy = 2

일때 기준 좌표에서 cy만큼 이동하면 비교 좌표로 이동하게 됩니다. 

따라서 x,y 중 하나만으로 맨해튼거리가 2인 경우에는 cx또는 cy 를 2로 나누어야합니다.

 

때문에 (dx, dy+cy//2) 의 좌표가 파티션인지 검사하면 됩니다.

 

완전탐색 조건

1. 맨해튼 거리가 1이라면 무조건 거리두기를 지키지 않는 것이다.
2. 맨해튼 거리가 2이라면, 파티션의 위치를 검사해야한다.
2-1. 파티션의 위치조건은 cx, cy의 절댓값이 각각1 이거나 0과 2 인 경우 두가지로 나뉜다.
2-2 절댓값이 각각 1인경우 dx+cx,dy 와 dx,dy+cy 를 검사한다.
2-3 절댓값이 0과 2일때는 ex) cx = 0 , cy = 2 라면 cy를 2로 나누고 난 뒤 (dx, dy+cy)를 검사한다
3. 2-2,2-3에서 검사한 파티션의 위치에 X가 없다면 거리두기를 지키지 않는 것이다.
4. 위의 과정을 각 예시에서 반복하고, 각 반복에서는 기준 응시자P1를 2차원 배열을 순회하며 순차적으로 설정해서 완전 탐색을 진행한다.

풀이코드

def solution(places):     answer = []     for idx,place in enumerate(places):         fail_flag = 0 #거리두기를 지키지 않았을때 플래그 1로 설정         dic = {}         cnt = 0         # 각 대기실에서 응시자 좌표와 응시자 수 찾기         for i in range(5):             for j in range(5):                 if place[i][j] == 'P':                     dic[cnt] = [i,j]                     cnt += 1         #기준응시자 설정         for c in range(0,cnt):             dx = dic[c][0]             dy = dic[c][1]             #비교응시자 설정             for d in range(c+1,cnt):                 nx = dic[d][0]                 ny = dic[d][1]                                  cx = nx-dx                 cy = ny-dy                 distance = abs(cx) + abs(cy)                                  # 맨해튼거리 검사                 if distance <= 2:                     #x성분 검사                     if abs(cx) == 2:                         if place[dx+cx//2][dy] != 'X':                             fail_flag = 1                                          elif abs(cx) == 1:                         if place[dx+cx][dy] != 'X':                             fail_flag = 1                     #y성분 검사                     if abs(cy) == 2:                         if place[dx][dy+cy//2] != 'X':                             fail_flag = 1                                          elif abs(cy) == 1:                         if place[dx][dy+cy] != 'X':                             fail_flag = 1                                                      if fail_flag == 0:             answer.append(1)         else:             answer.append(0)          return answer