[프로그래머스 : Lv.2] 거리두기 확인하기

👉 문제 링크

👉 풀이

거리두기를 안 지킨 경우
1) 'P' 사이의 거리가 1인 경우
2) 거리가 2이며, 행이 같고 'P' 사이에 파티션이 없는 경우
3) 거리가 2이며, 열이 같고 'P' 사이에 파티션이 없는 경우
4) 거리가 2이며, 행,열이 다르고 'P' 사이에 파티션이 없는 경우

탐색으로 해결할 수 있지 않을까?

BFS를 사용하려면
시작점이 필요하다. 이 문제에서는 P가 시작점이 되겠지?
P는 하나일 수도, 여러 개일수도 있기 때문에 P의 좌표를 리스트에 저장

탐색 시 'X'를 만나면 그 방향으로는 더이상 탐색 불가능이다.
반면, 'O'는 빈 테이블이므로 탐색 가능하다.

탐색 하다가 또 다른 'P'를 만난다면?
-> 현재 P와 만난 P의 거리를 판단하기 위해 거리를 더하며 저장해야함!

👉 전체 코드

from collections import deque

def bfs(p):
    start = []
    
    for i in range(5):
        for j in range(5):
            if p[i][j] == 'P':
                start.append((i,j))
    
    for s in start:
        que = deque([s])
        
        visited = [[False] * 5 for _ in range(5)]
        distance = [[0] * 5 for _ in range(5)]
        
        visited[s[0]][s[1]] = True
        
        while que:
            y,x = que.popleft()
            
            dx = [0,0,1,-1]
            dy = [ 1,-1,0,0]
            
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < 5 and 0 <= ny < 5 and not visited[ny][nx]:
                    
                        if p[ny][nx] == 'O':
                            que.append([ny,nx])
                            visited[ny][nx] = True
                            distance[ny][nx] = distance[y][x] +1
                        
                        if p[ny][nx] == 'P' and distance[y][x] <= 1:
                            return 0
    return 1
                
def solution(places):
    answer = []
    
    for i in places:
        answer.append(bfs(i))
    
    return answer