문제4 - 거리두기 확인하기 (Python)

프로그래머스

대기실 내 응시자 간 맨해튼 거리가 2 이하인지 확인하며, 파티션 설치 여부에 따른 예외 사례를 탐색 알고리즘으로 해결하는 문제입니다.

---

1. 나의 풀이 (Modular Approach)

room_size = 5

def recursive_pos_check(board, visited, pos, depth):
    # 거리 2까지 탐색 완료 시 종료
    if depth == 2:
        return True
    
    visited.append(pos)
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    for index in range(4):
        pos_r = pos[0] + dr[index]
        pos_c = pos[1] + dc[index]
        
        # 인덱스 범위 및 파티션 확인
        if pos_r < 0 or pos_c < 0 or pos_r >= room_size or pos_c >= room_size:
            continue
        if board[pos_r][pos_c] == 'X' or [pos_r, pos_c] in visited:
            continue
            
        # 응시자 발견 시 거리두기 위반
        if board[pos_r][pos_c] == 'P':
            return False
            
        # 빈 테이블일 경우 재귀적으로 추가 탐색
        if board[pos_r][pos_c] == 'O':
            if not recursive_pos_check(board, visited.copy(), [pos_r, pos_c], depth + 1):
                return False
                
    return True

def room_checker(room):
    for r in range(room_size):
        for c in range(room_size):
            if room[r][c] == 'P':
                # 각 응시자 위치에서 거리두기 준수 여부 확인
                if not recursive_pos_check(room, [], [r, c], 0):
                    return 0
    return 1

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

---

2.  오늘 배운 점 및 복기 노트

재귀 탐색에서의 불리언 결과 전파(Boolean Propagation) 및 조기 종료

탐색 함수에서 위반 사항을 발견했을 때, 단순히 값을 반환하는 것에 그치지 않고 상위 호출 스택으로 해당 결과를 즉시 전달(Short-circuiting)하는 로직의 중요성을 확인했습니다. 모든 경로를 끝까지 탐색하지 않고도 결론이 나는 시점에서 시스템 자원을 절약하며 논리적 오류를 방지할 수 있습니다.

가변 객체(Mutable Object)의 참조 공유로 인한 부수 효과 제어

Python의 리스트는 참조 타입이므로, 재귀 호출 시 동일한 visited 리스트를 넘겨주면 한쪽 분기에서의 방문 기록이 다른 분기의 탐색을 차단하는 부수 효과(Side Effect)가 발생합니다 .copy()를 통한 독립적인 상태(State) 전달은 DFS 환경에서 각 탐색 경로의 무결성을 보장해야 한다는 점을 배웠습니다.

기저 사례(Base Case)와 탐색 범위의 정합성

맨해튼 거리 2라는 제약 조건을 depth == 2라는 기저 사례로 치환하여 설계했습니다. 이때 탐색의 시작점(depth 0)과 끝점 간의 관계를 명확히 정의해야 인덱스 범위를 벗어나거나 불필요한 연산이 발생하는 것을 방지할 수 있음을 확인했습니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

6가지 위반 케이스의 직접 정의를 통한 전수 조사
교재는 범용적인 DFS 알고리즘 대신, 거리두기가 파괴되는 구체적인 상황을 6가지로 정의하여 직접 확인하는 방식을 제안합니다. 이는 복잡한 탐색 로직 없이도 문제를 해결할 수 있는 실전적인 시각을 제공합니다.

1. 거리 1 탐색: 상하좌우에 즉시 응시자가 있는 경우
2. 직선 거리 2 탐색: 상하좌우로 두 칸 떨어진 곳에 응시자가 있고, 그 사이가 파티션이 아닌 빈 테이블인 경우
3. 대각선 거리 2 탐색: 대각선 방향에 응시자가 있고, 인접한 두 경로 중 하나라도 파티션이 아닌 빈 테이블인 경우

순차적 탐색 방향을 활용한 연산 최적화
이중 루프가 (0,0)부터 (4,4)까지 우측 및 하단 방향으로 진행된다는 점에 착안하여, 이미 검증된 '위'나 '왼쪽'은 배제하고 '오른쪽'과 '아래' 방향의 위반 사례만 체크합니다. 이를 통해 중복 검사를 제거하고 검증 코드를 절반으로 줄일 수 있습니다.

인덱스 경계 검사의 변수화(Flagging) 기법
배열 탐색 시 가장 빈번하게 발생하는 IndexError를 방지하기 위해, 현재 좌표가 특정 검사가 가능한 위치인지를 미리 불리언(Boolean) 변수로 선언하는 기법입니다.

예를 들어 5x5 배열에서 거리 2인 칸을 확인해야 할 때, 다음과 같이 명시적인 변수를 선언합니다.

# 1. 현재 좌표에서 탐색 가능한 범위를 미리 정의 (Flagging)
isNotEndRow = idx_row != 4      # 아래로 한 칸(+1) 갈 수 있는가?
isBeforeThirdRow = idx_row < 3  # 아래로 두 칸(+2) 갈 수 있는가?
isNotEndCol = idx_col != 4      # 오른쪽으로 한 칸(+1) 갈 수 있는가?
isNotFirstCol = idx_col != 0    # 왼쪽으로 한 칸(-1) 갈 수 있는가?

# 2. 선언된 변수를 조건문의 필터로 사용
if isNotEndRow:
    # 안전하게 한 칸 아래(D)를 확인
    D = place[idx_row + 1][idx_col]
    if D == 'P': return 0  # 거리 1에 응시자가 있으면 즉시 종료
    
    if isBeforeThirdRow:
        # 안전하게 두 칸 아래(D2)를 확인
        D2 = place[idx_row + 2][idx_col]
        if D2 == 'P' and D != 'X': return 0 # 파티션이 없는데 사람이 있으면 위반

이 방식의 이점은 복잡한 조건문 내부에서 매번 idx_row + 2 < 5와 같은 수식을 계산할 필요가 없다는 것입니다. 코드 상단에서 검증 가능 여부를 미리 확정(Flagging)함으로써, 이후의 로직은 오직 거리두기 규칙 검증에만 집중할 수 있게 되어 가독성과 안정성이 동시에 향상됩니다.

 

---

4 . 책의 방식을 적용한 나의 풀이

def room_checker(room):
    for r in range(len(room)):
        for c in range(len(room)):
            if room[r][c] == 'P':
                isCanMoveDownOne = r != 4
                isCanMoveDownTwo = r < 3
                isCanMoveRightOne = c != 4
                isCanMoveRightTwo = c < 3
                isCanMoveLeftOne = c > 0

                # 밑에 사람이 있는 경우
                if isCanMoveDownOne:
                    if room[r + 1][c] == 'P':
                        return 0

                # 오른쪽에 사람이 있는 경우
                if isCanMoveRightOne:
                    if room[r][c + 1] == 'P':
                        return 0

                # 오른쪽 또는 밑이 파티션이 아닌데 오른쪽 아래에 사람이 있는 경우
                if isCanMoveRightOne and isCanMoveDownOne:
                    if room[r][c + 1] == 'O' or room[r + 1][c] == 'O':
                        if room[r + 1][c + 1] == 'P':
                            return 0

                # 왼쪽 또는 밑이 파티션이 아닌데 왼쪽 아래에 사람이 있는 경우
                if isCanMoveLeftOne and isCanMoveDownOne:
                    if room[r][c - 1] == 'O' or room[r + 1][c] == 'O':
                        if room[r + 1][c - 1] == 'P':
                            return 0

                #  밑이 파티션이 아닌데 밑의 밑에 사람이 있는 경우
                if isCanMoveDownTwo and room[r + 1][c] == 'O':
                    if room[r + 2][c] == 'P':
                        return 0

                #  오른쪽이 파티션이 아닌데 오른쪽의 오른쪽에 사람이 있는 경우
                if isCanMoveRightTwo and room[r][c + 1] == 'O':
                    if room[r][c + 2] == 'P':
                        return 0
    return 1


def solution(places):
    answer = []
    for room in places:
        answer.append(room_checker(room))

    return answer