(Python) - 프로그래머스(2021 카카오 채용연계형 인턴십) : 거리두기 확인하기

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

코딩테스트 연습 - 거리두기 확인하기

 

• 해설 :

5x5의 2차 배열이 주어진다. 원소는 P, O, X로 P는 사람, O는 빈자리, X는 파티션으로 이루어진다. 모든 사람들은 멘해튼거리 2 이내에 다른 사람이 존재하면 안된다. 다만, 다른 사람에게 가는 길이 파티션으로 완전히 막혀있다면 이는 거리두기를 지킨 것이 된다. 총 5개의 테스트케이스가 주어질 때 각 배열의 모든 사람들이 거리두기를 지키고있다면 1, 아니라면 0을 반환하면 된다.

 

 

 

• 풀이 :

배열의 모든 원소에 대해서 P를 만날 때마다 bfs를 실행하여 맨해튼거리 2 내에  X로 막혀있지 않고 다른 P로 갈 수 있는 길이 있는지 찾아본다. 만약 있다면 false를 리턴하고 asnwer에 0을 저장한 후 다음 배열로 넘어간다.

 

 

 

 

from collections import deque
 
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
 
 
def bfs(board,start):
    queue = deque()
    queue.append(start)
    c = [[-1 for _ in range(5)] for _ in range(5)]
    c[start[0]][start[1]] = 0
    while queue:
        x,y = queue.popleft()
        if c[x][y] == 3:
            return True
        if board[x][y] == "P" and [x,y] != start:
            return False
        for i in range(4):
            ax = x + dx[i]
            ay = y + dy[i]
            if 0 <= ax < 5 and 0 <= ay < 5:
                if c[ax][ay] == -1 and board[ax][ay] != "X":
                    queue.append([ax,ay])
                    c[ax][ay] = c[x][y] + 1
    return True
    
    
    
 
def solution(places):
    answer = [1 for _ in range(len(places))]
    for idx,p in enumerate(places):
        flag = True
        for i in range(5):
             for j in range(5):
                    if p[i][j] == "P":
                        if not bfs(p,[i,j]):
                            answer[idx] = 0
                            break
    return answer