[프로그래머스] 거리두기 확인하기 (python) - 2021 카카오 채용연계형 인턴십

🔗 문제링크

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

👩🏻‍💻 코드

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(place, x, y):
    visited = [[False] * 5 for _ in range(5)]
    q = deque()
    q.append((x, y, 0))
    visited[x][y] = True

    while q:
        x, y, cost = q.popleft()
        if cost == 2:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5:
                if visited[nx][ny]:
                    continue
                if place[nx][ny] == 'P':
                    return False
                if place[nx][ny] == 'O':
                    q.append((nx, ny, cost + 1))
                    visited[nx][ny] = True
    return True


def solution(places):
    answer = []

    for place in places:
        p = [list(place[i]) for i in range(5)]	# 대기실
        flag = True

        for i in range(5):
            for j in range(5):
                if p[i][j] == 'P':
                    if not bfs(p, i, j):  # 거리두기 안 지켰을 경우
                        flag = False
            if not flag:
                break
        if flag:
            answer.append(1)
        else:
            answer.append(0)

    return answer

📝 정리

'P'인 곳에서부터 2만큼 떨어진 곳까지만 확인해 주면 되므로 BFS로 풀면 될 것이라 판단했다. 생각한 알고리즘은 아래와 같다.

1. 대기실마다 확인하면서 'P'인 곳에서 bfs를 호출한다.
2. bfs 내에서 좌표 및 거리 (x, y, cost)를 큐에 넣는다.
   2-1. 거리가 2 미만이고 다음 방문할 곳이 'O'라면 큐에 넣는다.
   2-2. 거리가 2 미만이고 다음 방문할 곳이 'P'라면 False를 리턴한다.
   2-3. 거리가 2 면 중지한다.