[프로그래머스] Lv2. 거리두기 확인하기

문제 설명

P: 사람

X: 파티션

O: 테이블

사람과 사람 간의 거리는 맨해튼 거리 2 이하일 경우 코로나 바이러스 감염 예방 규칙을 위배하는 것이다.

맨해튼 거리란 두 사람의 좌표가 각각 (x1, y1), (x2, y2)일 때, |x1-x2| + |y1-y2|의 크기를 의미한다.

각각의 강의실에 배치된 사람들이 감염 예방 규칙을 잘 이행한 경우 1, 이행하지 않은 경우 0을 반환하고,

최종적으로 각각의 강의실에 대한 반환을 하나의 리스트에 담아 반환하면 된다.

 

제한 사항

제한 시간 : 10초

 

입출력 예시

 

첫 번째 시도

def check_border(place, i, j):
    border = [(-1,-1), (-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1)]
    for dx, dy in border:
        # 허용되는 좌표 안에서
        if 0 <= i+dx < 5 and 0 <= j+dy < 5:
            # 주변 좌표에 "P"가 있다면
            if place[i+dx][j+dy] == "P":
                if dx == 0 or dy == 0:
                    return 0
                # 원래 좌표(i,j)에서 해당 P좌표로 이동한 크기(dx, dy)에서 
                # (0, dy)만큼 이동한 좌표와 (dx, 0)만큼 이동한 좌표가 둘 다 파티션인지 확인
                if place[i][j+dy] != "X" or place[i+dx][j] != "X":
                    return 0
                else:
                    continue
            else:
                continue
                    
        else:
             continue
                
    return 1



def solution(places):
    answer = []

    for place in places:
        place_result = 1
        for i in range(5):
            for j in range(5):
                if place[i][j] == "P":
                    if check_border(place, i, j) == 0:
                        place_result = 0
                        break 
            if place_result == 0:
                break
        answer.append(place_result)
        
    return answer

해당 코드는 89.2%의 정답률을 보인다.  

각각의 강의실에 있는 인원들이 대한 좌표를 검사하고, 각각의 인원을 기준으로부터 맨해튼 거리가 2이하인 좌표를 나타내기 위해 가능한 이동을 dx, dy로 나타내야 한다.

대각선 상에 위치하는 P

# 허용되는 좌표 안에서
if 0 <= i+dx < 5 and 0 <= j+dy < 5:
    # 주변 좌표에 "P"가 있다면
    if place[i+dx][j+dy] == "P":
        if dx == 0 or dy == 0:
            return 0
        # 원래 좌표(i,j)에서 해당 P좌표로 이동한 크기(dx, dy)에서 
        # (0, dy)만큼 이동한 좌표와 (dx, 0)만큼 이동한 좌표가 둘 다 파티션인지 확인
        if place[i][j+dy] != "X" or place[i+dx][j] != "X":
            return 0
        else:
            continue
    else:
        continue

그러나, 위 코드는 맨해튼 거리가 1인 상하좌우와 맨해튼 거리가 2인 대각선에 위치한 좌표값에 대해서만 처리한 코드였다.

직선 경로 상의 맨해튼 거리가 2인 좌표들에 대한 처리도 해주어야 한다.

 

두 번째 시도

def check_border(place, i, j):
    border = [(-1,-1), (-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(2,0),(0,2),(-2,0),(0,-2)]
    for dx, dy in border:
        # 허용되는 좌표 안에서
        if 0 <= i+dx < 5 and 0 <= j+dy < 5:
            # 주변 좌표에 "P"가 있다면
            if place[i+dx][j+dy] == "P":
                if abs(dx) == 2 or abs(dy) == 2:
                    if place[i+dx//2][j] == "X":
                        continue
                    elif place[i][j+dy//2] == "X":
                        continue
                    else:
                        return 0
                # 원래 좌표(i,j)에서 해당 P좌표로 이동한 크기(dx, dy)에서 
                # (0, dy)만큼 이동한 좌표와 (dx, 0)만큼 이동한 좌표가 둘 다 파티션인지 확인
                elif place[i][j+dy] != "X" or place[i+dx][j] != "X":
                    return 0
                else:
                    continue
            else:
                continue
                    
        else:
             continue
                
    return 1



def solution(places):
    answer = []

    for place in places:
        place_result = 1
        for i in range(5):
            for j in range(5):
                if place[i][j] == "P":
                    if check_border(place, i, j) == 0:
                        place_result = 0
                        break 
            if place_result == 0:
                break
        answer.append(place_result)
        
    return answer

check_border 함수를 수정하여 직선 상의 맨해튼 거리가 2인 좌표들을 처리하기 위해 border 리스트에 (dx, dy) 요소들을 추가해 주었다.

 

# 주변 좌표에 "P"가 있다면
if place[i+dx][j+dy] == "P":
    if abs(dx) == 2 or abs(dy) == 2:
        if place[i+dx//2][j] == "X":
            continue
        elif place[i][j+dy//2] == "X":
            continue
        else:
            return 0

P와 P 사이에 X 존재

만약, 직선 상의 거리가 2인 좌표에 "P"가 존재한다면 "P"와 "P"사이에 "X"값이 존재해야 할 것이다. 위 코드에 이러한 의미를 갖는 코드를 추가해 주었다.

 

키 포인트

📌 좌표의 이동에 대해 (dx, dy)를 사용하는 방식

생각해보기

📌 만약 맨해튼 거리의 제한이 2보다 큰 수가 주어진다면?

→ dx, dy의 경우에 수는 더욱 많아질 것이다. 위의 코드처럼 모든 좌표의 이동에 대한 경우의 수를 일일이 넣기 힘들 수 있다.