[프로그래머스] 거리두기 확인하기 (Lv 2)

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

프로그래머스

 

아, 진짜 너무 심각하게 bfs가 약하다.

심지어 내가 인턴 코테로 푼 기출인데... 왜이리 헤맨건지... 진짜 코테 연습 많이 해서 감 좀 올려야겠다.

아마 당시에는 다른 방법으로 그냥 계산때린거 같다.

조금 쓰는 법을 바꿔서 돌면 안되는 케이스를 continue로 빼줘야 이해하기 쉬울거 같다.

from collections import deque
mv_list = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(place, row, col):
    visited = [[False for _ in range(5)] for _ in range(5)]
    queue = deque()
    visited[row][col] = True
    queue.append((row, col, 0))
    
    while queue:
        curr = queue.popleft()
        if curr[2] > 2:
            continue
        elif curr[2] >= 1 and place[curr[0]][curr[1]] == 'P':
            return False
        else:
            for cur_mv in mv_list:
                nr = curr[0] + cur_mv[0]
                nc = curr[1] + cur_mv[1]
                
                if nr < 0 or nr > 4 or nc < 0 or nc > 4:
                    continue
                if visited[nr][nc]:
                    continue
                if place[nr][nc] == 'X':
                    continue
                visited[nr][nc] = True
                queue.append((nr, nc, curr[2] + 1))
    return True
        
def check(place):
    for row in range(5):
        for col in range(5):
            if place[row][col] == 'P':
                if bfs(place, row, col) == False:
                    return False
    return True

def solution(places):
    answer = []
    
    for place in places:
        if check(place):
            answer.append(1)
        else:
            answer.append(0)
    return answer