[Python] 2021 카카오 인턴십 기출문제 - 거리두기 확인하기

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

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

[ 알고리즘 ]

BFS

 

[ 접근 방법 ]

* 조건 *

1. 벽이 없는 경우에

2. 맨해튼 거리가 2 이하이고

3. 응시자가 앉아있는 자리(P)이면 거리두기 실패

 

맨해튼 거리를 표시하는 가중치 값(weight)을 x,y 좌표와 함께 큐에 넣어준다.

 

그 후 응시자가 앉아있는 자리(P)인 노드부터 BFS를 진행한다.

이때 파티션("X")가 아닌 경우에만 큐에 넣어준다.

 

만약 큐에서 꺼낸 데이터의 가중치(맨해튼 거리)가 1이상 2이하이고, 그 좌표에 응시자(P)가 앉아있다면 거리두기 실패이다.

 

[ 코드 ]

from collections import deque

def check(a, b, graph):
    visited = [[0] * 5 for _ in range(5)]
    que = deque()
    que.append((a, b, 0))
    visited[a][b] = 1

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

    while que:
        x, y, weight = que.popleft()

        if weight > 2:
            break
        if 1 <= weight <= 2 and graph[x][y] == "P":
            return False

        for i in range(4):
            xx = dx[i]
            yy = dy[i]

            if x + xx < 0 or y + yy < 0 or x + xx >= 5 or y + yy >= 5:
                continue

            if visited[x + xx][y + yy] == 0 and graph[x + xx][y + yy] != "X":
                que.append((x + xx, y + yy, weight + 1))
                visited[x][y] = 1
    return True


def solution(places):
    answer = []

    for place in places:
        c = 0
        for x in range(5):
            for y in range(5):
                if place[x][y] == 'P':
                    if not check(x, y, place):
                        answer.append(0)
                        c = -1
                        break

            if c == -1:
                break
        if c == 0:
            answer.append(1)

    return answer