알고리즘 코드카타 118 - 거리두기 확인하기

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

프로그래머스

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

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

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

 

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

 

def solution(places):
    result = []
    for place in places:
    	pass
    return result

 

먼저 places 리스트를 순회하면서 각 방 별로 데이터를 분리한다. 

 

# def solution(places):
#     result = []
#     for place in places:
        for cols in range(5):
            for rows in range(5):
                if place[cols][rows] == 'P':
    return result

 

각 방들의 모든 자리를 순서대로 순회하면서 사람이 앉은 자리 (=P)인 경우 탐색을 시도한다.

 

# def solution(places):
#     result = []
#     for place in places:
          answer = []
#         for cols in range(5):
#             for rows in range(5):
#                 if place[cols][rows] == 'P':
                    answer.append(check(rows, cols, place))
        result.append(1 if all(answer) else 0)
    return result

 

탐색을 위한 함수인 check(작성예정)을 통해서 자리의 주번을 탐색하고 answer에 True or Fales를 입력한다. check함수는 각 자리를 순회하면서 현재 자리에 있는 사람이 거리두기를 지키고 있으면 True, 지키고 있지 않으면 False를 출력한다.

result에는 answer의 모든 원소가 True일 경우에는 1을 입력하도록 해서 현재 방의 모든 인원을 검사한다.

 

def check(r, c, place):
    if r - 1 >= 0 and place[c][r - 1] == 'P':
        return False
    if r - 2 >= 0 and place[c][r - 2] == 'P' and place[c][r - 1] != 'X':
        return False
    if r + 1 < 5 and place[c][r + 1] == 'P':
        return False
    if r + 2 < 5 and place[c][r + 2] == 'P' and place[c][r + 1] != 'X':
        return False
    if c - 1 >= 0 and place[c - 1][r] == 'P':
        return False
    if c - 2 >= 0 and place[c - 2][r] == 'P' and place[c - 1][r] != 'X':
        return False
    if c + 1 < 5 and place[c + 1][r] == 'P':
        return False
    if c + 2 < 5 and place[c + 2][r] == 'P' and place[c + 1][r] != 'X':
        return False
    if r - 1 >= 0 and c - 1 >= 0 and place[c - 1][r - 1] == 'P' and (place[c - 1][r] != 'X' or place[c][r - 1] != 'X'):
        return False
    if r - 1 >= 0 and c + 1 < 5 and place[c + 1][r - 1] == 'P' and (place[c + 1][r] != 'X' or place[c][r - 1] != 'X'):
        return False
    if r + 1 < 5 and c - 1 >= 0 and place[c - 1][r + 1] == 'P' and (place[c - 1][r] != 'X' or place[c][r + 1] != 'X'):
        return False
    if r + 1 < 5 and c + 1 < 5 and place[c + 1][r + 1] == 'P' and (place[c + 1][r] != 'X' or place[c][r + 1] != 'X'):
        return False
    return True

 

bfs탐색을 해도 됐지만 탐색 범위가 얼마 되지 않으니 전부 세보기로 했다. 반복문의 위에부터 순서대로,

현재 위치의 왼쪽에 다른 사람이 있는 경우,

현재 위치의 왼쪽 두번째 칸에 다른 사람이 있고 사이에 칸막이가 없는 경우,

현재 위치의 오른쪽에 다른 사람이 있는 경우,

현재 위치의 오른쪽 두번째 칸에 다른 사람이 있고 사이에 칸막이가 없는 경우,

현재 위치의 위쪽에 다른 사람이 있는 경우,

현재 위치의 위쪽 두번째 칸에 다른 사람이 있고 사이에 칸막이가 없는 경우,

현재 위치의 아래쪽에 다른 사람이 있는 경우,

현재 위치의 아래쪽 두번째 칸에 다른 사람이 있고 사이에 칸막이가 없는 경우,

현재 위치의 왼쪽 위칸에 다른 사람이 있고 왼쪽과 위에 하나라도 칸막이가 없는 경우,

현재 위치의 왼쪽 아래칸에 다른 사람이 있고 왼쪽과 아래에 하나라도 칸막이가 없는 경우,

현재 위치의 오른쪽 위칸에 다른 사람이 있고 오른쪽과 위에 하나라도 칸막이가 없는 경우,

현재 위치의 오른쪽 아래칸에 다른 사람이 있고 오른쪽과 아래에 하나라도 칸막이가 없는 경우,

각각  False를 반환하도록 한다.

모든 반복문을 통과한 경우에는 Ture를 반환하게 되며 반환된 값은 answer에 입력된다.

완료!

 

깔끔한 풀이는 아니었지만 아무튼 시간문제에도 걸리지 않았으니 성공이라고 해두자.