[카카오 코테 2021 | python] 거리두기 확인하기

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/81302#fn1
• level2
• 2021 카카오 채용연계형 인턴십

 

Q1) 이 문제를 어떻게 해석하셨나요?
A1) 주어진 5개의 5x5 대기실에서 응시자 간의 거리두기 준수 여부를 확인하는 문제입니다. 각 자리에는 응시자(P), 빈 테이블(O), 파티션(X)이 있으며, 응시자 사이의 맨해튼 거리가 2 이하일 때 파티션이 없다면 거리두기 위반으로 간주합니다.

Q2) 이 문제를 어떻게 풀 계획이신가요? 
A2)
- 각 대기실을 2차원 배열로 탐색합니다.
- 응시자(P)가 있는 위치를 기준으로, BFS 탐색을 수행해, 맨해튼 거리 ≤ 2의 위치에 있는 다른 P를 확인합니다. 그 사이에 X(파티션)이 없으면 실패, 있으면 통과로 간주합니다.
- 거리두기를 지키지 않은 경우가 하나라도 있다면 0, 모두 지켰다면 1을 결과에 추가합니다.
- 최종적으로 대기실 5개에 대한 1차원 결과 리스트를 반환합니다.

Q3) BFS 알고리즘에 대해 설명해주세요.
A3) 그래프나 트리에서 최단 경로 탐색, 레벨 순회, 가까운 노드부터 탐색할 때 사용하는 알고리즘입니다. 큐 자료구조를 이용해 탐색 순서를 유지하고, 모든 경로를 탐색할 수 있습니다.

 

💡 최적화된 코드

place = [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], 
         ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], 
         ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], 
         ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], 
         ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

from collections import deque

def is_valid(place):
    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':
                continue # 사람(P)이 아니면 건너뜀

            queue = deque()
            queue.append((i, j, 0))  # (x, y, 거리)

            visited = [[False] * 5 for _ in range(5)]
            visited[i][j] = True

            while queue:
                x, y, dist = queue.popleft()

                if dist >= 1 and place[x][y] == 'P':
                    return 0  # 다른 사람과 맨해튼 거리 2 이하, 파티션 없이 마주침

                if dist >= 2:
                    continue  # 거리 2 넘으면 더 볼 필요 없음

                for dir in range(4):
                    nx = x + dx[dir]
                    ny = y + dy[dir]

                    if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny]:
                        if place[nx][ny] != 'X':  # 💡 파티션(X)이면 진행하지 않음!
                            visited[nx][ny] = True
                            queue.append((nx, ny, dist + 1))
    return 1

def solution(places):
    return [is_valid(place) for place in places]