[프로그래머스] 2021 카카오 채용연계형 인턴십 02.거리두기 확인하기

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

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

 

문제설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예를 들어,

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

 

입출력 예

 

풀이

BFS를 이용하여 시작점에서 거리 2이하인 모든 지점을 탐색하고 P를 발견하면 거리두기가 잘 지켜지지 못한 것이고,
P를 발견하지 못하면 거리두기를 잘 지켰다고 판단하는 로직을 구성하였다.

 

def solution(places):
    answer = []

    for place in places:
        start = []
        # Start가 빈 경우, P가 없는 경우는 거리두기를 잘 지킨것이다.
        flag = True
        for y in range(5):
            for x in range(5):
                if place[y][x] == 'P':
                    start.append((y, x))

시작점(P)을 기준으로 거리 2 이내에 위치한지 확인하기 위해서 모든 P의 위치를 start list에 저장하였다.

 

def bfs(y, x, place):
    direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    dq = deque()
    dq.append((y, x))

    check = [[False for _ in range(5)] for _ in range(5)]
    check[y][x] = True

    max_dist = 2

함수 bfs의 인자로 start에서 받은 좌표와 책상의 배치상황을 나타내는 place를 넘겨주었다.
direction, dq, check 등을 선언하고 최대로 이동할 거리 2를 설정하였다.

 

while dq and max_dist > 0:
        dqsize = len(dq)
        max_dist -= 1
        while dqsize:
            y, x = dq.popleft()
            dqsize -= 1

max_dist는 남은 이동할 수 있는 거리로 이동할 수 있는 거리가 0보다 큰 경우에만 탐색을 진행한다.
먼저 첫 while문에서 dq의 size를 저장하고 2번째 while문에서 그 사이즈만큼만 탐색하는 것으로

while (1번 이동한 좌표) -> while (2번 이동한 좌표) -> while (3번 이동한 좌표) -> ....
이런 식으로 bfs의 탐색 속도를 조절할 수 있다.

 

	for j in range(4):
                next_y, next_x = y + direction[j][0], x + direction[j][1]
                if 0 <= next_y < 5 and 0 <= next_x < 5 and check[next_y][next_x] is False:
                    if place[next_y][next_x] == 'P':
                        return False
                    elif place[next_y][next_x] == 'O':
                        check[next_y][next_x] = True
                        dq.append((next_y, next_x))

    return True

다음은 기존 bfs와 동일하게 범위 안에서 방문한적 없는 경우에만 방문한다.
P를 만나면 False를 반환하고 O인 경우에만 deque에 추가한다.

P를 만나지 못하고 모든 while문을 통과하면 True를 반환하는 것으로 거리두기를 잘 지켰다는 것을 나타낸다.

 

        for i in start:
            flag = bfs(i[0], i[1], place)
            if not flag:
                break

        if flag:
            answer.append(1)
        else:
            answer.append(0)

    return answer

마지막으로 원래 있던 solution함수에서 결과값을 받아 answer리스트에 추가하면 된다.

 

 

전체 코드

from collections import deque

def bfs(y, x, place):
    direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    dq = deque()
    dq.append((y, x))

    check = [[False for _ in range(5)] for _ in range(5)]
    check[y][x] = True

    max_dist = 2
    while dq and max_dist > 0:
        dqsize = len(dq)
        max_dist -= 1
        while dqsize:
            y, x = dq.popleft()
            dqsize -= 1
            for j in range(4):
                next_y, next_x = y + direction[j][0], x + direction[j][1]
                if 0 <= next_y < 5 and 0 <= next_x < 5 and check[next_y][next_x] is False:
                    if place[next_y][next_x] == 'P':
                        return False
                    elif place[next_y][next_x] == 'O':
                        check[next_y][next_x] = True
                        dq.append((next_y, next_x))

    return True




def solution(places):
    answer = []

    for place in places:
        start = []
        flag = True
        for y in range(5):
            for x in range(5):
                if place[y][x] == 'P':
                    start.append((y, x))

        for i in start:
            flag = bfs(i[0], i[1], place)
            if not flag:
                break

        if flag:
            answer.append(1)
        else:
            answer.append(0)

    return answer

start 리스트가 빈 경우에는 거리두기를 잘 지킨 것이기 때문에 매 번 flag의 초기값을 True로 선언해야하는데
제일 처음 1번만 선언하는 바람에 정답이 나오지 않아서 오래 걸렸다.

배열의 크기가 5*5로 고정되어 있고 최대 거리를 2로 제한하기 때문에 2칸 떨어진 지점의 좌표들을 직접 체크해서 풀 수 있는 문제지만 그렇게 푸는 경우에 최대 거리를 늘리게되면 풀기가 어려워진다.

최대 거리가 변해도 풀 수 있는 방법으로 익혀두자.