[프로그래머스] 거리두기 확인하기

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

 

어려워서 구글링하여 참고하였고 제출은 안 함..!

 

from collections import deque

LENGTH = 5

def bfs(p):
    start = []
    # 시작점이 되는 P 좌표 구하기
    for i in range(LENGTH):
        for j in range(LENGTH):
        	# 응시자가 앉아있는 자리 P가 시작점
            if p[i][j] == 'P':
                start.append([i, j])
    for s in start:
        queue = deque([s])  # 큐에 초기값
        visited = [[0]*LENGTH for i in range(LENGTH)]   # 방문 처리 리스트
        distance = [[0]*LENGTH for i in range(LENGTH)]  # 경로 길이 리스트
        visited[s[0]][s[1]] = 1
        
        while queue:
            y, x = queue.popleft()
            dx = [-1, 1, 0, 0]  # 좌우
            dy = [0, 0, -1, 1]  # 상하

            for i in range(4):
            	# 다음 진행 위치 구하기
                nx = x + dx[i]
                ny = y + dy[i]

				# 대기실(5) 이내 방문하지 않은 자리
                if 0<=nx<LENGTH and 0<=ny<LENGTH and visited[ny][nx] == 0:
                	# 'O'이면 빈 자리로 다음'P'가 나올 때까지의 거리에 해당하므로 거리를 더해 줌
                    if p[ny][nx] == 'O':
                        queue.append([ny, nx])
                        visited[ny][nx] = 1
                        distance[ny][nx] = distance[y][x] + 1
                    # 'P'일 때 맨해튼 거리가 2 이내이면 거리두기 실패: 0
                    if p[ny][nx] == 'P' and distance[y][x] <= 1:
                        return 0
                    # 'X'이면 파티션으로 가로막힌 것이므로 거리두기에 해당
                # 방문한 곳은 큐에서 꺼내짐
    # P에서 BFS가 끝나면 1 반환 (다른 곳의 P를 만났는데 맨해튼 거리 이내이면 먼저 0 반환)
    return 1


def solution(places):
    answer = []
    for i in places:
        answer.append(bfs(i))
    return answer

 

참고: https://velog.io/@sem/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LEVEL2-%EA%B1%B0%EB%A6%AC%EB%91%90%EA%B8%B0-%ED%99%95%EC%9D%B8%ED%95%98%EA%B8%B0-Python

[프로그래머스] LEVEL2 거리두기 확인하기 (Python)