LV 2: 거리두기 확인하기

문제 링크

LV 2: 거리두기 확인하기

구현 방식

• 대기실(board)을 2중 for문으로 순회하며, board[i][j] == 'P'인 경우에 check 함수를 호출한다

  • check의 return 값이 False인 경우, 거리두기를 지키고 있지 않은 경우이므로 result에 0을 append하고 다음 대기실 확인
  • check의 return 값이 True인 경우, 거리두기를 지키고 있는 경우임
    
    

• check(x, y)는 bfs를 기반으로 탐색하는데, 맨해튼 거리가 2 이하인지 확인 및 칸막이('X')를 발견한 경우 더이상 진행하지 않도록만 해주면 된다

코드

from collections import deque

def solution(places):
    
    dx = (0, 0, -1, 1)
    dy = (-1, 1, 0, 0)
    
    def check(x, y):
        queue = deque([]); queue.append((x, y))
        visit = [[False] * 5 for _ in range(5)]; visit[x][y] = True
        
        while queue:
            cx, cy = queue.popleft()
            for i in range(4):
                nx = cx + dx[i]; ny = cy + dy[i]
                if 0 <= nx < 5 and 0 <= ny < 5:
                    if abs(x - nx) + abs(y - ny) <= 2: 
                        if not visit[nx][ny]:
                            if board[nx][ny] == 'P': return False
                            elif board[nx][ny] == 'X': continue
                            else: queue.append((nx, ny)); visit[nx][ny] = True
        return True
                    
    
    result = []
    for place in places:
        
        board = []
        for p in place:
            board.append(list(p))
            
        break_flag = False
        for i in range(5):
            for j in range(5):
                if board[i][j] == 'P':
                    if not check(i, j): result.append(0); break_flag = True; break
            if break_flag: break
        
        if break_flag: continue
        else: result.append(1)
        
    return result