프로그래머스 거리두기 확인하기 - 반례 검증기

문제 링크 → 프로그래머스 - 거리두기 확인하기

문제는 5x5 대기실에서 사람이 서로 맨해튼 거리 2 이내에 있으면서 가림막 없이 마주보면 거리두기 위반으로 간주하는 것이다. 간단히 말해:

• P끼리 인접(맨해튼 거리 1)해 있으면 무조건 위반
• P끼리 맨해튼 거리 2일 때, 그 사이가 O 또는 X냐에 따라 다름
• O는 빈자리, X는 파티션(가림막)

✅ 내가 작성한 풀이

나는 BFS를 사용하지 않고, 단순한 조건문 기반의 전수 조사 방식으로 풀었다. 핵심은 두 가지 조건이다:

1. 사람(P)이 상하좌우로 붙어 있으면 위반
2. 빈자리(O) 기준으로 상하좌우에 P가 2명 이상 붙어 있으면 위반

def solution(places):
    answer = []
    for place in places:
        people = set()
        for r, row in enumerate(place):
            for c, ch in enumerate(row):
                if ch == 'P':
                    people.add((r, c))

        violation = False
        for r, row in enumerate(place):
            for c, ch in enumerate(row):
                if ch == 'P':
                    # 상하좌우에 다른 P가 있으면 거리 1 위반
                    if len({(r-1, c), (r+1, c), (r, c-1), (r, c+1)} & people) > 0:
                        violation = True
                        break
                elif ch == 'O':
                    # O 주변에 P가 2명 이상이면 거리 2 위반
                    if len({(r-1, c), (r+1, c), (r, c-1), (r, c+1)} & people) > 1:
                        violation = True
                        break
            if violation:
                break

        answer.append(0 if violation else 1)
    return answer

---

❗ GPT가 제기한 반례 주장

처음에 GPT는 이렇게 주장했다:

"P가 대각선에 위치하고, 그 사이에 O가 있는 경우에는, 각 O가 P 한 명만 인접하므로 너 코드로는 탐지하지 못한다."

예시:

P O
O P

이 상황에서 GPT는 "(0,1)과 (1,0)은 O고, 각각 P 한 명만 인접하므로 위반을 탐지 못한다"고 말했지만…

---

✅ 내가 반박했고, GPT가 납득함

직접 해당 예시를 코드로 돌려보니:

• (0,1) = O, 인접한 P = (0,0), (1,1) → P 2명 붙음 ✅
• (1,0) = O, 인접한 P = (0,0), (1,1) → P 2명 붙음 ✅

즉, 충분히 내 코드에서 위반으로 탐지 가능했다.

또한 GPT가 주장한 다른 반례들도 살펴봤지만,

• 거리 3 이상이거나
• 결국 O에 P가 2명 붙어 있는 구조였기 때문에

모두 내 코드로 커버 가능했고, 진짜 반례는 존재하지 않았다.

결국 GPT도 "네 코드가 맞고 반례는 없었다"고 납득했다 😉

---

🔁 BFS 풀이도 함께 보기

참고로 BFS로 푸는 방식은 아래와 같다:

def solution(places):
    from collections import deque

    def is_valid(place):
        for r in range(5):
            for c in range(5):
                if place[r][c] != 'P':
                    continue
                queue = deque([(r, c, 0)])
                visited = {(r, c)}

                while queue:
                    y, x, dist = queue.popleft()
                    if 0 < dist <= 2 and place[y][x] == 'P':
                        return 0
                    if dist >= 2:
                        continue
                    for dy, dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                        ny, nx = y + dy, x + dx
                        if 0 <= ny < 5 and 0 <= nx < 5 and (ny, nx) not in visited:
                            if place[ny][nx] != 'X':
                                queue.append((ny, nx, dist+1))
                                visited.add((ny, nx))
        return 1

    return [is_valid(place) for place in places]

BFS 방식은 거리 기반으로 탐색이 가능해 직관적이고 일반화에 좋지만,
이 문제 크기(5x5)에선 내 코드가 훨씬 간단하고 빠르다.

---

✅ 결론

• GPT도 사람이다(?) → 가끔은 틀린다
• 조건문 방식만으로도 거리두기 위반 여부를 완벽하게 판단 가능하다
• 반례라고 주장한 예시들을 직접 반박하면서 코드의 정확성을 검증할 수 있었다
• BFS도 훌륭한 방법이지만, 꼭 써야 할 필요는 없다!

---

필요 이상으로 BFS를 끌어오는 대신, 문제 구조에 맞는 간단한 조건문 조합이
얼마나 강력할 수 있는지를 증명한 재미있는 경험이었다 😎