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

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

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

# 최근 5월 "2021 카카오 채용연계형 인턴십" 코딩테스트에 출제된 따끈따끈한 문제이다.

 

# 빈 테이블이 있든 말든, 파티션이 있든 말든 상관없이 그냥 bfs를 돌려서 각각 사람들 사이의

  거리를 구한다음 거리가 2이내에 사람이 존재하면 0을 return하고 모든 사람 사이의 거리가

  3 이상이면 1을 return 하는 식으로 아이디어를 구상했다.

 

# bfs함수는 특별한 것은 없고 n번째 대기실에서 n[mx][my]가 'X'가 아니고(파티션이 아니고)

  (nx, ny)를 방문하지 않았으면, m[nx][ny]에 현재까지의 거리(m[x][y]) + 1을 넣어준다.

 

1. 5x5 대기실 n개가 한번에 입력되므로 n번째 대기실마다 bfs를 돌려준다. (18번째 줄)

   반복문을 돌며 n[i][j]가 'P'이면 p에 (i, j)좌표를 넣어준다. (응시자가 앉아있는 자리)

 

2. 반복문을 돌며 p에 있는 모든 응시자들 사이의 거리를 bfs함수를 통해 구해준다.

   n번째 대기실에 있는 응시자들 한명 한명을 대상으로 '각각' bfs함수를 실행시킨다.

 

3. dist에 응시자들 사이의 거리가 저장될 것이고, 자기 자신을 제외하고

   다른 응시자들 사이의 거리가 1~2이면 (32번째 줄)

   거리두기가 지켜지지 않고 있는 것이므로 answer에 0을 넣고 tf = True, break해준다.

   다른 응시자들을 확인해야하지만, tf가 True이면 확인하지 않고 바로 break를 해주고 

   다음 대기실을 확인한다. (36 ~ 37번째 줄)

    * 한 명이라도 거리두기를 지키지 않고 있으면, 다른 응시자들이 모두 지키고 있더라도

       0을 return해야 하기 때문에 바로 break를 해준다.

 

4. 모든 응시자들을 확인했는데 tf가 False이면 모두 거리두기를 잘 지키고 있으므로

   answer에 1을 append해준다. (38 ~ 39번째 줄)

   최종적으로 모든 대기실을 확인한 뒤 answer을 return해준다.

 

from collections import deque
def solution(places): 
    dx, dy = [0,0,-1,1], [-1,1,0,0]
    def bfs(i, j, m, visited):
        q.append((i, j))
        visited[i][j] = True
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < 5 and 0 <= ny < 5 and n[nx][ny] != 'X' and not visited[nx][ny]:
                    m[nx][ny] = m[x][y] + 1
                    q.append((nx, ny))
                    visited[nx][ny] = True
        return m

    answer = []
    for n in places:
        p = []
        tf = False
        for i in range(5):
            for j in range(5):
                if n[i][j] == 'P':
                    p.append([i, j])      
        
        for i, j in p:
            m = [[0] * 5 for _ in range(5)]
            q = deque()
            visited = [[False] * 5 for _ in range(5)]
            dist = bfs(i, j, m, visited)
            for cx, cy in p:
                if (cx, cy) != (i, j) and 1 <= dist[cx][cy] <= 2:
                    answer.append(0)
                    tf = True
                    break
            if tf:
                break
        if not tf:
            answer.append(1)
            
    return answer

(프로그래머스 level: 2)