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

문제

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

프로그래머스

 

---

 

주요 아이디어

대기실에 있는 모든 응시자들이 맨해튼 거리 2 초과로 앉아있거나 / 응시자 사이가 파티션으로 막혀있는지를 판단하는 문제이다.

• 모든 강의실 자리를 서칭하면서, 하나라도 예외가 존재하면 return 0 / 존재하지 않을 경우 return 1
• BFS 방식으로 모든 응시자의 자리로부터 맨해튼 거리 2 이내에 파티션을 사이에 두지 않은 응시자가 존재하는지 확인

 

---

 

코드 구현 (Python 3)

 

from collections import deque

# 모든 강의실 서칭하면서 하나라도 예외 있으면 return 0
# 모든 시작 지점 통과해야 return 1

def bfs_search(graph):
    # 원본 강의실 copy 및 리스트로의 변환
    graph_copy = []
    for row in graph:
        graph_copy.append([x for x in row])
    
    distance = [[0] * len(graph[0]) for _ in range(len(graph))]
    direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    
    start = []
    n, m = len(graph), len(graph[0])
    for i in range(n):
        for j in range(m):
            if graph_copy[i][j] == "P":
                start.append((i, j))

    for s in start:
        queue = deque([s])
        graph_copy[s[0]][s[1]] = 'X'

        while queue:
            y, x = queue.popleft()
            
            # 인접 노드 탐색
            for dx, dy in direction:
                nx = x + dx; ny = y + dy
                
                # 벽 체크 & 방문 체크
                if 0 <= nx < m and 0 <= ny < n and graph_copy[ny][nx] != 'X':
                    # 다른 참가자일 경우 & 맨해튼 거리 2 이하일 경우
                    if graph_copy[ny][nx] == 'P' and distance[y][x] + 1 <= 2:
                        return 0
                    
                    # 방문한 적 없을 경우 큐에 넣고 거리 더해주기
                    if graph_copy[ny][nx] == "O":
                        queue.append([ny, nx])
                        # 미리 방문처리
                        graph_copy[ny][nx] = "X"

                        # 거리 계산
                        distance[ny][nx] = distance[y][x] + 1
            
    # 모든 케이스 통과
    return 1



def solution(places):
    answer = []
    
    # i개의 강의실
    for place in places:
        answer.append(bfs_search(place))
                
    return answer

 

 

---

 

제출 결과