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

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

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

 

from collections import deque
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def solution(places):
    answer = []
    for room in places:
        answer.append(check(room))
    return answer


def check(room):
    person = []
    for i in range(5):
        for j in range(5):
            if room[i][j] == 'P':
                person.append((i, j))
    if not person:
        return 1
    return bfs(person, room)


def bfs(person, room):
    for i, j in person:
        q = deque()
        q.append((i, j))
        visited = [[0] * 5 for _ in range(5)]
        visited[i][j] = 1
        while q:
            x, y = q.popleft()
            if visited[x][y] == 3:
                continue
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny]:
                    if room[nx][ny] != 'X':
                        visited[nx][ny] = visited[x][y] + 1
                        q.append((nx, ny))
                    if room[nx][ny] == 'P':
                        return 0
    return 1

 

2021 카카오 인턴십, BFS
1. places의 각 room마다 check
2. check : 'P'의 위치를 person리스트에 넣어준다.
    - person이 없으면 빈 공간 return 1 (거리두기 지킴)
    - person이 있으면 bfs
3. bfs : 각 person마다 진행
    - 'X'가 아니라면 q에 append
    - 'P'라면 return 0 (거리두기 안 지킴)
    - 모든 person이 진행되고 for문을 탈출했으면 return 1 (거리두기 지킴)