[프로그래머스] Lv2. 거리두기 확인하기

🔍 문제

풀이

문제의 조건에서 배열의 크기가 전부 다 5x5이다. 중복으로 완전 탐색을 하면서 심지어 백트래킹을 하지 않아도 시간초과가 안 날 것 같다.

처음에는 P의 위치에서 맨해튼 거리내의 P들을 전부 조사한 다음에 그 사이에 X가 있는지의 여부를 판별하려고 했다.

OOPOO
OPXPO
PXPXP
OPXPO
OOPOO

그런데 거리두기가 지켜지고 있는 완벽한 상황을 그려보니, 그냥 P의 상하좌우에 전부 파티션이 있으면 나머지 P가 어느 위치에 있든 상관없이 현재의 P는 무조건 거리두기를 지키고 있는 거였다.

1. 상하좌우 전부다 파티션이면 통과
2. 상하좌우에 P가 하나라도 있다면 맨해튼 거리가 지켜지지 않으로 탈락
3. 상하좌우에 파티션이 없는 곳이 있다면
   3-1. 파티션 없는 곳 상하좌우에 P가 하나라도 있다면 탈락
   3-2. 파티션 없는 곳 상하좌우에 P가 하나도 없다면 통과

위의 조건을 지켜 탐색하면 된다. 3-1.의 과정에서는 파티션이 없는 위치를 찾은 원래 기준의 P 위치는 파티션이 없는 곳에서 상하좌우 탐색할 때 제외해야 한다.

"""
1. 애초에 P 주변이 전부다 X면 확인할 필요가 없음
2. 근데 만약에 P 주변(상하좌우)에 P가 하나라도 있다면 바로 return 0
3. P는 없지만 O가 하나라도 있다면 O 주변의 상하좌우 확인
4. 5x5라서 중복으로 확인해도 시간초과는 안 날듯? 
"""

def solution(places):
    answer = []
    
    def distance(place, _x, _y):
        # 상하좌우 먼저 확인
        # 전부다 X면 통과 True 반환
        # P가 하나라도 있으면 False 반환
        # O가 하나라도 있으면 그 상하좌우도 확인 P 있으면 바로 False
        queue = [(_x, _y, 'P')]
        while queue:
            x, y, s = queue.pop(0)
            for nx, ny in (x-1, y), (x+1, y), (x, y+1), (x, y-1):
                if nx<0 or ny<0 or nx>=5 or ny>=5:
                    continue
                if s == 'O' and (nx, ny) == (_x, _y):
                    continue
                if place[nx][ny] == 'P':
                    return False
                if s == 'P' and place[nx][ny] == 'O':
                    queue.append((nx, ny, 'O'))
                    
        return True
    
    # 각 place의 각각의 P에 대해 확인
    def each_place(place):
        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P' and not distance(place, i, j):
                    return 0
        return 1
                    
    for place in places:
        answer.append(each_place(place))
    return answer