[알고리즘] 프로그래머스 81302 '거리두기 확인하기' _ 파이썬

프로그래머스 81302 거리두기 확인하기
https://programmers.co.kr/learn/courses/30/lessons/81302
난이도 : 레벨 2
유형 : BFS!

문제

크기가 5*5인 다섯개의 대기실이 존재
각 응시자들끼리는 맨해튼 거리 2 이하로 앉을 수 없다.
대신 사이에 파티션이 있어서 맨해튼 거리 2를 거쳐서 서로 닿을 수 없다면 가능.

풀이

1. 각 응시자들끼리의 거리

'BFS를 이용해 한 응시자에서 한 칸 씩 나아가다가 맨해튼 거리 2 이하인 칸에서 다른 응시자들을 만나는가'라는 로직을 생각하면서 풀었다.

2. 파티션의 유무

어차피 맨해튼 거리의 공식이 |r1 - r2| + |c1 - c2|이므로 응시자가 있는 자리에서 상하좌우로 인접한 칸으로 이동하다가 파티션이 있으면 그 칸에서는 이동하지 않도록 한다.

정답 코드

from collections import deque

def bfs(places, sx, sy):
    dq = deque([(sx, sy)])

    visited = [[0] * 5 for _ in range(5)]
    #네방향으로 가면서 X(파티션)일때는 안가도록 해서 P(응시자)를 만나면 False
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[sx][sy] = 1

    while dq:
        print(dq)
        x, y = dq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #5*5칸 안에 존재하는지, 맨해튼 거리가 2 이하인지, 방문한 적 있는지 
            if 0 <= nx < 5 and 0 <= ny < 5 and (abs(nx-sx) + abs(ny-sy) <= 2) and visited[nx][ny] == 0:
            	#응시자 만난 경우 False 반환
                if places[nx][ny] == 'P':
                    print(nx, ny)
                    return False
                #빈칸(P도 아니고 X도 아니고)인 경우 dq에 값 넣고 계속 진행
                if places[nx][ny] == "O":
                    visited[nx][ny] = 1
                    dq.append((nx, ny))
    #다 만족한 경우
    else:
        return True 


def solution(places):
    answer = [1] * 5
    #5개의 방을 실행하면서 
    for t in range(5):
        B = False
        for i in range(5):
            for j in range(5):
                if places[t][i][j] == 'P':
                #한 번 이라도 False가 나온다면 그 방은 거리두기가 지켜지지 않았으므로 0으로 바꿔줌
                    if bfs(places[t], i, j) == False:
                        B = True
                        answer[t] = 0
                        break

    print(answer)
    return answer