[프로그래머스] 거리두기 확인하기 python (*)

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

출처 : 프로그래머스

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

---

from collections import deque

def bfs(p):
    start = [] # P(사람) 마다 bfs해야함
    
    for i in range(len(p)):
        for j in range(len(p)):
            if p[i][j] == "P":
                start.append((i,j))
    # start p좌표마다
    for s in start:
        q = deque()
        q.append(s) # 큐에 시작 p좌표 삽입
        visited = [[0]*5 for _ in range(5)]
        distance = [[0]*5 for _ in range(5)]
        visited[s[0]][s[1]] = 1 # 처음 p좌표 방문처리
    
        while q:
            x, y = q.popleft()
            dx = [-1, 1, 0, 0]
            dy = [0, 0, -1, 1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<5 and 0<=ny<5 and not visited[nx][ny]:
                    if p[nx][ny] == 'O': # 빈 책상이면
                        q.append((nx,ny))
                        visited[nx][ny] = 1 # 방문처리
                        distance[nx][ny] = distance[x][y] + 1 #거리 업데이트

                    elif p[nx][ny] == 'P':
                        distance[nx][ny] = distance[x][y]+1
                        if distance[nx][ny]<=2:
                            return 0
    return 1
                            
        
def solution(places):
    answer = []
    for i in places:
        answer.append(bfs(i))
    return answer

풀이

bfs로 풀이했다.

p(사람) 마다 주변에 p(사람) 이 맨해튼 거리가 2 이하인 거리에 있는지를 확인해야 한다.

파티션이 있으면 상하좌우 이동이 안 되는 것이고, O(빈 책상) 이 있으면 이동 가능하다.

p마다 bfs를 수행해야 하니, p의 좌표를 모두 start에 넣어서 관리한다.

 

 

.

이는 나중에 다시 풀어보도록 하자.