[programmers/py] 거리두기 확인하기

거리두기 확인하기

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

문제 설명

5x5 크기 5개의 대기실에 참가자들이 앉아있습니다.
5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다.
1. 응시자들끼리 맨해튼 거리가 2 이하로 앉는 경우 거리두기 위반입니다.
2. 아래 예시를 통해 다른 경우를 확인 할 수 있습니다.

맨해튼 거리

두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다

풀이

최대 길이가 5인 배열이라 완점 탐색을 통해 해결 가능합니다.

1. 각 참가자들이 앉은 위치를 보관합니다.
2. 참가자들의 자리를 확인하며 거리두기를 위반한지 확인합니다.
   2-1. 거리가 1인 경우
   2-2. 참가자들 사이에 파티션(X)가 없는 경우

def check(p):
    arr = []
    for i in range(5):
        for j in range(5):
            if p[i][j] == "P":
                arr.append((i,j))
    
    # 두 사람 거리 비교
    for x,y in arr:
        for x1,y1 in arr:
            
            # 맨허튼 거리
            dist = abs(x-x1) + abs(y-y1)
            
            # 3이상 또는 같은 p면 스킵
            if dist == 0 or dist > 2:
                continue
            
            # 거리가 1
            if dist == 1:
                return 0
            # 열이 같은데 파티션이 없음
            if x == x1 and p[x][int((y+y1)/2)] != "X":
                return 0
            # 행이 같은데 파티션이 없음
            if y == y1 and p[int((x+x1)/2)][y] != "X":
                return 0
            # 대각선
            if x != x1 and y != y1:
                if p[x1][y] != "X" or p[x][y1] != "X":
                    return 0
    return 1

def solution(places):
    answer = []
    for i in places:
        answer.append(check(i))
    return answer