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

문제

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

소스코드

from collections import deque
def bfs(place):
    visited = [[0] * 5 for _ in range(5)]
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P' and not visited[i][j]:
                visited[i][j] = 1
                q = deque()
                q.append([i,j,0])
                while q:
                    x,y,dist = q.popleft()
                    
                    if dist >= 2:
                        continue
                        
                    for k in range(4):
                        xx = x + dx[k]
                        yy = y + dy[k]
                        if 0<=xx<5 and 0<=yy<5 and not visited[xx][yy]:
                            if place[xx][yy] == 'O':
                                visited[xx][yy] = 1 
                                q.append([xx,yy,dist+1])
                            if place[xx][yy] == 'P' and dist <= 1:
                                return 0
    return 1
                                 
def solution(places):
        answer = []
        for p in places:
            answer.append(bfs(p))
        return answer

설명

📌 아이디어

• bfs 탐색으로 문제를 해결한다.
• bfs 탐색시 좌표와 거리를 같이 큐에 넣고 체크하면, 좀 더 쉽게 맨해튼 거리 조건을 해결할 수 있다.

📌 문제 풀이 로직

• 총 5개의 대기실이 있으므로 5번의 동일한 bfs 로직을 돌려서 결과값을 리턴해준다.
• 방문 확인을 체크할 배열을 초기화해준다.
• place 대기실 2차원 배열을 돌면서 사람이 나오면 조건에 맞는지 확인해준다. (이때 처음 시작은 거리가 나 자신 0 이다.)
• pop 한 값이 거리가 2가 넘으면 맨해튼 거리 조건을 일치하지 않으므로 패스해준다.
• 상하좌우를 체크해서 빈테이블이면 큐에 넣는다.
• 상하좌우 체크해서 사람이 나오면
  • 거리를 체크해서 일치하지 않으면 0을 리턴하고 종료한다.
  • 조건에 맞아도 체크하지 않는다. 왜냐면 사람1을 기준으로 조건에 맞지 않는 사람을 체크하는 것이기 때문이다. 현재 사람1을 체크하는 도중 사람2에 대해 확인한 후 조건에 맞으면 사람1은 조건에 맞게 앉은 것이다. 사람2는 사람2 차례가 오면 그때 체크하면 된다.
• 모든 조건을 다 만족하면 1을 리턴해준다.

📌 예시

no	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	O	X
3	O	X	X	O	P
4	P	X	P	O	X

 

place[0][0]이 P 이기 때문에 상하좌우 체크한다.

place[1][0] 이 O 빈공간이기 때문에 q에 넣어준다. 

place[0][1] 은 X 이기때문에 그뒤에 사람이 와도 상관없어서 패스한다.

place[2][0]은 빈공간이지만 place[0][0] 기준으로 거리가 2가 된다. 맨헤튼 거리 조건에 일치하지 않으므로 패스된다.

place[0][0]의 P는 모든 조건을 만족한다.

 

이런식으로 체크를 해주고 조건에 맞지 않으면 바로 0을 리턴해면서 함수를 종료시켜 시간을 절약할 수 있다.