프로그래머스 Lv. 2 거리두기 확인하기 Python [반례 포함]

문제 링크

https://school.programmers.co.kr/tryouts/72050/challenges

정답 코드

from collections import deque
def solution(places):
    answer = []
    # 5 * 5
    # 거리 2 이하는 안돼
    # P 응시자
    # O는 빈 테이블
    # X는 파티션
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    def isValid(nr, nc):
        return 0 <= nr < 5 and 0 <= nc < 5
    for place in places:
        isNotValid = False
        for sr in range(5):
            for sc in range(5):
                if place[sr][sc] == "P":
                    V = [[-1 for _ in range(5)] for _ in range(5)]
                    V[sr][sc] = 0
                    q = deque([(sr, sc)])
                    while q:
                        r, c = q.popleft()   
                        for d in range(4):
                            nr = r + dr[d]
                            nc = c + dc[d]
                            if isValid(nr, nc) and place[nr][nc] != "X" and V[nr][nc] == -1:
                                V[nr][nc] = V[r][c] + 1
                                if place[nr][nc] == "P":
                                    if V[nr][nc] < 3:
                                        isNotValid = True
                                        answer.append(0)
                                        break
                                else:
                                    q.append((nr, nc))
                        if isNotValid:
                            break
                if isNotValid:
                    break
            if isNotValid:
                break
        if isNotValid == False:
            answer.append(1)
    return answer

풀이 방법

- bfs를 이용해서 "P"인 경우에 다른 "P"를 찾아서 떠난다.

- 이미 거리두기 어겼을 때는 더 순회하지 못하게 isNotValid를 True로 만드는 것이 핵심이다.

반례

느낀점

- 안되면 내 코드에서 Tab이 지정된 위치에서 잘 된건지 확인해야 한다.