[프로그래머스] 2021카카오 인턴십 LV2 거리두기 확인하기 (Python)

문제 링크

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

나의 풀이

1. places를 돌며 'P'인 경우 bfs를 수행한다.
2. bfs에서 queue에는 [x, y, distance] 형식으로 넣고 처음에 distance는 0으로 설정한다.
   1. 이후 while문을 돌며 pop한 distance에 +1을 해주고, 해당 값이 3이 되면 거리두기 2를 지킨 경우이기 때문에 멈춘다.
   2. 만약 상하좌우 탐색 중 distance가 2 이하인데 'P'를 만나면 거리두기가 지켜지지 않은 경우이다.
3. bfs탐색 결과 False가 나오면 거리두기를 지키지 않은 것이기 때문에 모든 반복문을 멈추고 false를 리턴한다.
4. bfs탐색 결과 True면 거리두기를 잘 지킨 경우다.

Code

  

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

# BFS

from collections import deque

def bfs(row, col, place):
    visited = [[0 for _ in range(5)] for _ in range(5)]

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

    q = deque()
    q.append([row, col, 0])
    visited[row][col] = 1

    while q:
        x, y, dist = q.popleft()

        nd = dist + 1

        if nd >= 3:
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 5 and 0 <= ny < 5 and visited[nx][ny] == 0:
                visited[nx][ny] = 1

                if dist <= 2 and place[nx][ny] == 'P':
                    return False
                if place[nx][ny] == 'O' and nd == 1:
                    q.append([nx, ny, dist + 1])

    return True


def solution(places):
    answer = []

    for place in places:
        flag = 1

        for i in range(5):
            for j in range(5):
                if place[i][j] == 'P':
                    if not bfs(i, j, place):
                        flag = 0

                if not flag:
                    break

            if not flag:
                break
        answer.append(flag)

    return answer

Git

https://github.com/youngh0/Algorithm/blob/master/kakao/2021_internship/LV2_distance_check.py