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

문제 요약

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

 

1. 5x5 크기의 5개의 대기실이 2차원 배열(places)로 주어진다. 

2. 배열은 P 응시자, 0 빈 공간, X 파티션으로 구성되어 있다. 

3. 거리두기를 위해 응시자들 간 맨해튼 거리가 2 이하인 대기실은 0, 그렇지 않은 대기실은 1을 반환한다. (*맨해튼 거리 = |x1 - x2| + |y1 - y2| )

4. 응시자들 간 맨해튼 거리가 2 이하여도 그 사이에 파티션이 있다면 0을 반환하지 않는다. 

 

 

접근

첫번째 접근

P를 기준으로 2만큼의 깊이까지 bfs를 돌려 P가 있는지 확인해보려고 했다. 

손코딩으로 써보고 나니, 코드가 복잡한 것 같아 더 좋은 방법이 있는지 생각해보았다. 

 

두번째 접근

배열을 그려놓고 보니 O을 기준으로 봤을 때, 상하좌우에 P가 2개 이상 존재한다면 맨하튼 거리가 2가 된다는 것을 알게 되었다.

또한 맨하튼 거리가 1인 경우는 P가 나란히 있는 경우이기 때문에 이 경우도 따져줘야 한다. 

 

1. places 배열을 삼중 포문을 돌려 P일 때는 check_next 함수를 실행시켜 인접한 곳에 P가 있다면 True를 반환해주었고

2. O일 때는 check_over 함수를 실행시켜 인접한 곳에 P가 2개 이상있다면 True를 반환해주었다.

 

코드

def solution(places):
    answer = []

    def check_next(x, y, idx):
        for a, b in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= a < 5 and 0 <= b < 5 and places[idx][a][b] == "P":
                return True
        return False

    def check_over(x, y, idx):
        cnt = 0
        for a, b in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= a < 5 and 0 <= b < 5 and places[idx][a][b] == "P":
                cnt += 1

        if cnt >= 2:
            return True
        return False

    for idx, place in enumerate(places):
        breakcheck = 0
        for i in range(5):
            for j in range(5):
                if place[i][j] == "P" and check_next(i, j, idx):
                    breakcheck = 1
                    break

                elif place[i][j] == "O" and check_over(i, j, idx):
                    breakcheck = 1
                    break

            if breakcheck == 1:
                break

        if breakcheck == 1:
            answer.append(0)
        else:
            answer.append(1)

    return answer