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

문제 설명

제한사항 및 입출력

풀이

왜 이런 문제만 보면 bfs에 사로잡히는건지 모르겠다. 틀에 갇힌 사고가 되어버린 것만 같지만 그래도 가장 먼저 생각한 알고리즘으로 풀이해보기로 했다..

각 응시자의 자리에서 bfs를 돌리면서 맨해튼 거리 내에 사람이 있는지 확인해주었다. while 루프 내에 for문으로 queue의 길이를 재서 각 탐색을 구분하여 맨해튼거리를 쟀다. bfs를 돌릴 때 파티션은 그냥 안가면 올바른 맨해튼 거리를 도출할 수 있다. 이후 한 명이라도 위반했다면 0으로 세팅하고 ans 배열에 넣어주었다.

 

내 코드

from collections import deque

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

def bfs(matrix, sx, sy):
    queue = deque([(sx, sy)])
    visited = set([(sx, sy)])
    
    cnt = 1
    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                # 5 * 5 조건
                if 0 <= nx < 5 and 0 <= ny < 5:
                    # 파티션이 아니고 방문한 적 없으면 탐색
                    if matrix[nx][ny] != 'X' and (nx, ny) not in visited:
                        # 맨해튼 거리 2 내로 사람이 있으면 false 반환
                        if matrix[nx][ny] == 'P' and cnt <= 2:
                            return False
                        visited.add((nx, ny))
                        queue.append((nx, ny))
        
        cnt += 1
        if cnt > 2:
            return True

def solution(places):
    ans = []
    
    # 모든 대기실의 모든 사람을 시작점으로 bfs 돌리기
    for place in places:
        flag = 1
        for j in range(5):
            for k in range(5):
                if place[j][k] == 'P':
                    # 한 명이라도 안 지켜졌으면 break 후 0으로 세팅
                    if bfs(place, j, k) == 0:
                        flag = 0
                        break
        
            if not flag:
                break
        
        # 모두 지켜졌으면 1
        ans.append(flag)
        
    return ans

 

풀이에 대한 별다른 특이점은 없기 때문에 시간 복잡도만 설명해보자면, 대기실의 수, 격자의 행열이 모두 5로 고정되어있기 때문에 O(5 * 5 * 5 * 25 * 4)정도 일 것 같다. (25는 모든 사람이 꽉 차있다고 가정할때)

고찰

풀이하고 나니 그냥 각 참석자들을 기준으로 맨해튼 거리를 계산하는 방법이 더 쉬울 것 같아서 풀이해보았다.

 

# 맨해튼 거리 2까지 직접 확인 
def check_place(place):
    for i in range(5):
        for j in range(5):
            if place[i][j] != 'P':
                continue

            # 거리 1 (상하좌우)
            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < 5 and 0 <= nj < 5 and place[ni][nj] == 'P':
                    return 0

            # 거리 2 (직선)
            for di, dj in [(2, 0), (-2, 0), (0, 2), (0, -2)]:
                ni, nj = i + di, j + dj
                mi, mj = i + di // 2, j + dj // 2  # 중간 칸
                if 0 <= ni < 5 and 0 <= nj < 5:
                    if place[ni][nj] == 'P' and place[mi][mj] == 'O':
                        return 0

            # 거리 2 (대각선)
            for di, dj in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < 5 and 0 <= nj < 5 and place[ni][nj] == 'P':
                    # 대각선일 때 두 중간 칸 중 하나라도 O면 파티션이 없는 판정
                    if place[i][nj] == 'O' or place[ni][j] == 'O':
                        return 0

    return 1

def solution(places):
    return [check_place(place) for place in places]

굳이 bfs까지는 필요없었던 것 같다..! 시간 복잡도도 bfs에서는 한 번 더 깊게 탐색해야하는 경우도 줄어들어 조금 더 최적화 된 것 같다.