거리두기 확인하기

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

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

def is_ok(people, partition):
    for i in range(len(people)):
        for j in range(i + 1, len(people)):
            if abs(people[i][0] - people[j][0]) + abs(people[i][1] - people[j][1]) <= 2: # too close
                if people[i][0] == people[j][0]: # vertical
                    if (people[i][0], (people[i][1] + people[j][1])/2) not in partition:
                        return 0
                elif people[i][1] == people[j][1]: # horizontal
                    if ((people[i][0] + people[j][0])/2, people[i][1]) not in partition:
                        return 0
                else: # cross
                    if (people[i][0]+1, people[i][1]) not in partition:
                        return 0
                    if people[i][1] > people[j][1]: # left side
                        if (people[i][0], people[i][1]-1) not in partition:
                            return 0
                    else: # right side
                        if (people[i][0], people[i][1]+1) not in partition:
                            return 0

            if people[i][0] - people[j][0] > 1: # no more close people
                break
    return 1


def solution(places):
    answer = []
    
    for place in places:
        people = []
        partition = []
        result = 1
        for i in range(len(place)):
            for j in range(len(place[i])):
                if place[i][j] == 'P':
                    people.append((i, j))
                elif place[i][j] == 'X':
                    partition.append((i, j))
        
        answer.append(is_ok(people, partition))
        
    return answer

 

크기와 distance가 작아 경우의 수가 적기 때문에 쉽게 풀 수 있었다.

거리가 2 이내이며 파티션이 없는 경우 return 0을 해야하는데, 그러한 조건은

• 가로 일직선 2 칸 안에 있는 경우
• 세로 일직선 2 칸 안에 있는 경우
• 맞붙은 대각선 상에 있는 경우

로 나누어 볼 수 있다.

people 배열을 만들 때 앞에서부터 순서쌍을 채워 나갔으므로, 앞에서 확인한 조건은 뒤의 사람에서 다시 확인할 필요가 없기 때문에 결국 result가 0이 될 수 있는 경우는 아래 4가지로 한정된다.

• 가로 일직선 2 칸 안에 있으며 그 사이에 파티션이 없는 경우
• 세로 일직선 2 칸 안에 있으며 그 사이에 파티션이 없는 경우
• 대각선 상에 위치하면서 위의 사람보다 밑의 사람의 x 좌표가 더 크고, 옆, 아래 공간에 파티션이 없는 경우
• 대각선 상에 위치하면서 위의 사람보다 밑의 사람의 x 좌표가 더 작고, 옆, 아래 공간에 파티션이 없는 경우

특히 위의 두 조건은 바로 연달아 있건, 한 칸 띄워 앉았건, 두 위치 사이에 파티션이 있는지 확인해도 상관은 없다.