[프로그래머스] 거리두기 확인하기 (파이썬)

📕 문제

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

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

 

💡 풀이법

1. bfs를 이용해서 풀었다.

2. deq에 x와 y그리고 시작점과의 거리인 d를 담는다.

3. 사방을 확인하며 좌표를 넘어가지 않고 방문하지 않았으면 방문체크를 해주고 만약 해당 위치가 p인데 거리가 2보다 작다면 거리두기를 하지 않았으므로 바로 0을 리턴한다.

4. 만약 거리가 1이면 더 갈 수 있기 때문에 해당 좌표와 거리를 deq에 담아준다.

 

from collections import deque

def bfs(room, x, y):
    deq = deque([(x, y, 0)])
    visited = [[0 for _ in range(5)] for _ in range(5)]
    dxy = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    while deq:
        x, y, d = deq.popleft()
        visited[x][y] = True
        
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            nd = d + 1

            if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny]:
                visited[nx][ny] = True
                
                if room[nx][ny] == 'P':
                    if nd <= 2:
                        return 0

                elif room[nx][ny] == 'O':
                    if nd == 1:
                        deq.append((nx, ny, nd))
    return 1

def solution(places):
    answer = []
    for room in places:
        flag = False
        for i in range(5):
            for j in range(5):
                if room[i][j] == 'P':
                    if not bfs(room, i, j):
                        answer.append(0)
                        flag = True
                        break
            if flag:
                break
        else:
            answer.append(1)

    return answer