거리두기 확인하기 (Programmers 81302)

🧑‍💻 거리두기 확인하기

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

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

예를 들어,

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]

🧑‍💻 해결방법

• 맨하튼 거리와 두 사람의 좌표를 표시하는 리스트를 만든다.
• 중요한 부분은 맨해튼 거리가 2일 때이기 때문에 조건문을 넣어주는 것이 중요하다.
• 대각선 체크, 같은 x 혹은 y 좌표에 위치했을 때 사이에 'O'가 존재하는지 여부에 따라 True, False 체크를 해주어야한다.

🧑‍💻 코드

def manhatten(p1, p2):
   res = abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
   return res


def queen(board):
   new_board = [r for r in board]
   ppl = [] # 사람이 있는 곳의 좌표
   man = [] # manhatten distance

   for i in range(5):
       for j in range(5):
           if new_board[i][j] == 'P':
               ppl.append([i, j])

   for i in range(len(ppl)):
       for j in range(i + 1, len(ppl)):
           man.append([manhatten(ppl[i], ppl[j]), ppl[i], ppl[j]])

   for chk in man:
       if chk[0] == 0:
           continue
       elif chk[0] == 1:
           really = 0
           return really
       elif chk[0] == 2:
           if new_board[chk[1][0]][chk[2][1]] == 'O' or new_board[chk[2][0]][chk[1][1]] == 'O':
               really = 0
               return really
           # x 좌표 같은지
           if chk[1][0] == chk[2][0] :
               mid = max(chk[1][1], chk[2][1]) - 1
               if new_board[chk[1][0]][mid] == 'O' :
                   really = 0
                   return really
           # y 좌표 같은지
           elif chk[1][1] == chk[2][1] :
               mid = max(chk[1][0], chk[2][0]) - 1
               if new_board[mid][chk[1][1]] == 'O' :
                   really = 0
                   return really
       else :
           continue
   really = 1
   return really

def solution(places):
   result = []
   for wait in places:
       result.append(queen(wait))
   return result

🧑‍💻 총평

• 코테를 볼 때는 3시간 정도 걸려서 30개의 테스트케이스 중에서 1개만 틀렸었다.
• 이제 다시 풀 때 프로그래머스 시스템과 IDE의 반환값에 차이가 있어서 오류인가 싶었는데 테스트케이스가 변경되어 있었다.
• 문제를 바로잡고 다시 풀어서 해결.
• DFS, BFS에 대해서 잘 모르지만 다른 사람들은 이 문제를 DFS, BFS 로 풀어낸 것을 보아하니 다른 알고리즘의 스킬들이 필요한 듯 하다.
• 그래도 깔끔하게 해결.