[프로그래머스 Lv.2] 거리두기 확인하기 - Python

코딩테스트 연습 - 거리두기 확인하기

POINT

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

맨해튼 거리

한 칸 = 거리 1

즉, 두 칸 이하로 떨어져 있으면 거리가 2이하이다.

거리가 2 이하지만 파티션으로 막혀서 허용되는 CASE

식으로 따지면 크게 3가지..

1.거리가 2지만 위의 경우에 속하지 않거나, 2.거리가 1이면 허용되지 않는다.

풀이

1. 대기실을 하나씩 확인한다.
2. 한 대기실의 모든 사람 위치를 리스트에 저장한다.
3. 큐를 사용하여 서로의 거리를 확인한다.
4. answer 리스트에 답을 추가하고, 다음 대기실을 확인한다. (2부터 반복)

def check_distance(place, people):
    # 리스트 제일 왼쪽 사람을 기준으로, 나머지 사람과 비교한다. (queue)
    while people:
        r1, c1 = people.pop(0)
        for r2, c2 in people:
            distance = abs(r1-r2) + abs(c1-c2)
            
            # 거리가 2이면
            if distance == 2:
                # PXP (가로)
                if r1 == r2 and place[r2][max(c1, c2)-1] == "X": continue
                # PXP (세로)
                if c1 == c2 and place[max(r1, r2)-1][c2] == "X": continue
                # PXPX (대각선)
                if place[r1][c2] == "X" and place[r2][c1] == "X": continue
                return False
            
            # 거리가 1이면
            if distance == 1: return False
    
    return True
    
def solution(places):
    answer = []
    
    for place in places:
        people = []
        flag = True
        # 사람 위치 저장
        for i in range(5):
            for j in range(5):
                if place[i][j] == "P":
                    people.append((i,j))
                
        flag = check_distance(place, people)
        if flag: answer.append(1)
        else: answer.append(0)
    
    return answer