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

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

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

간단했지만 실수를 좀 많이했다.. p에서 다른 p를 찾는데 여기서 실수를 저질렀다.. 거리가 3 이상이면 찾지 않아도 되기에 종료 조건을 dist >=3일 경우 종료해 주었다. 제출해 보니 하나도 맞지 못했다. 당연했다.. 현재 거리를 기준으로 해야하기에 dist>=2로 해주는게 맞았다. 현재 거리가 2이면 다음에 찾는 지역은 거리는 3이 되므로 찾지 않아도 된다... 이것때문에 삽질을 조금 했다. 다시 수정해서 제출하니 성공했다.
로직은 bfs사용했다. 중간에 탈출이 쉽기 때문이다. bfs를 이용해서 좌석에 앉아 있는 사람을 기준으로 4방향으로 탐색을 진행했고 중간에 탈출 조건은 현재 거리가 2이상일 때 탈출했다(더 이상 탐색 진행 x). p를 찾았고 그 거리가 2이하이면 멘하탄거리를 지키지 않았기에 거리두기를 지키지 않은것이다. 주어진 조건에서 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 아래의 경우이다. 첫번째 P인 (0,0)에서 탐색을 진행해보면 (1,1)위치에 P를 탐색하지 못하게 하면 된다. 조건을 빈테이블(O)일 경우만 움직이게 하므로써 해결 할 수 있다.

ex)
px
xp

이 후 방문했던 곳은 재방문 못하도록 처리해주면서 몇명의 사람이 거리두기를 지키지 않았는지 확인하면 된다.

코드

from collections import deque
dr = [1,-1,0,0]
dc = [0,0,1,-1]
def bfs(start_r,start_c,grid):
    q = deque()
    visited = [[False] * 5 for _ in range(5)]
    q.append((start_r, start_c,0))
    visited[start_r][start_c] = True
    distance = [[10000] * 5 for _ in range(5)]
    tmp_p = []
    while q:
        now_r, now_c, dist = q.popleft()
        # 2이상인 거리는 볼 필요가 없다.
        if dist>=2:
            break
        for i in range(4):
            next_r = now_r + dr[i]
            next_c = now_c + dc[i]
            next_dist = dist +1
            if 0<=next_r<5 and 0<=next_c<5 and not visited[next_r][next_c]:
                visited[next_r][next_c] = True
                if grid[next_r][next_c] == 'O':
                    q.append((next_r,next_c, next_dist))
                # 만약 다음 방문 할 곳에 사람이 앉아있으면
                elif grid[next_r][next_c] == 'P':
                    #거리가 2보다 작거나 같다면
                    if dist<=2:
                        return False
    
    return True
        

def solution(places):
    answer = []
    for i in places:
        grid = []
        for k in i:
            grid.append(list(k))
        flag = False
        for rr in range(5):
            for cc in range(5):
                # 응시자가 앉아있는 자리를 기준으로 맨하탄 거리가 2이하인 응시자를 찾는다.
                if grid[rr][cc] == 'P':
                    if not bfs(rr,cc,grid):
                        flag = True
                        break
        if not flag:
            answer.append(1)
        elif flag:
            answer.append(0)
        
    return answer