문제 보기 · Level 2 · 2021 카카오 채용연계형 인턴십 · 정답률 49% · 푼 사람 17,518명 (2026-09-30 기준)1
문제
5×5 대기실 5개가 P(응시자), O(빈 테이블), X(파티션)로 주어진다. 두 응시자 사이의 맨해튼 거리가 2 이하면 거리두기 위반이다. 단, 두 자리 사이가 파티션으로 막혀 있으면 괜찮다. 대기실마다 모두 지키면 1, 한 명이라도 어기면 0을 담아 돌려준다.
- 대기실 5개, 각각 5×5
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
구현과 시뮬레이션: 격자 좌표, 맨해튼 거리, 두 칸 사이의 칸 확인.
1단계 · 작은 예로 손으로 풀기
거리가 2 이하인 두 사람의 위치 관계는 세 가지뿐이다.
| 모양 | 예 | 위반인가 |
|---|---|---|
| 바로 옆(거리 1) | PP |
늘 위반 |
| 한 칸 건너 일직선(거리 2) | POP, PXP |
가운데가 X면 괜찮고, 아니면 위반 |
| 대각선(거리 2) | 위 PO, 아래 OP |
나머지 두 칸이 모두 X면 괜찮고, 하나라도 X가 아니면 위반 |
대각선은 두 모서리 칸 중 어느 쪽으로든 건너갈 수 있어서, 두 길을 모두 막아야 괜찮다.
가로 a칸, 세로 b칸 떨어진 두 칸 사이의 가장 짧은 길은 \(\binom{a+b}{a}\)개라(순열과 조합의 격자 경로), 대각선은 2개, 일직선 두 칸은 1개다.
2단계 · 가장 단순한 방법과 그 속도
대기실 하나에 응시자는 최대 25명이라 두 명씩 짝지어도 300쌍이다. 대기실 5개면 1,500쌍이다. 모든 쌍을 확인해도 된다.
3단계 · 핵심 아이디어
응시자 좌표를 모두 모은 뒤, 모든 두 명에 대해 거리를 구하고 1단계의 세 경우로 판정한다.
- 거리 1: 위반.
- 거리 2이고 같은 줄: 가운데 칸
(r, (c1+c2)//2)가 X가 아니면 위반. - 거리 2이고 같은 칸(열): 가운데 칸
((r1+r2)//2, c)가 X가 아니면 위반. - 거리 2이고 대각선: 모서리 두 칸
(r1, c2),(r2, c1)중 하나라도 X가 아니면 위반.
다른 방법: 응시자마다 X가 아닌 칸으로만 두 걸음까지 퍼져 나가(BFS) 다른 응시자를 만나는지 본다. 이 방법은 너비 우선 탐색(BFS)에서 다룬다.
X 칸을 뺀 격자를 그래프로 보면, 1단계의 세 경우는 “X를 피해 가는 최단 거리가 2 이하면 위반”이라는 규칙 하나로 묶인다(경로와 연결성). X가 없으면 이 거리는 맨해튼 거리와 같고, X는 길을 막아 거리를 늘릴 뿐 줄이지는 못한다.
4단계 · 코드 흐름
- 대기실마다 P의 좌표를 모은다.
- 모든 두 명 쌍에 대해 거리와 위치 관계로 위반인지 본다.
- 위반이 하나라도 있으면 0, 없으면 1을 답에 넣는다.
5단계 · 파이썬 코드
def solution(places):
answer = []
for room in places:
people = [(r, c) for r in range(5) for c in range(5) if room[r][c] == "P"]
ok = 1
for i in range(len(people)):
for j in range(i + 1, len(people)):
(r1, c1), (r2, c2) = people[i], people[j]
d = abs(r1 - r2) + abs(c1 - c2)
if d == 1:
ok = 0
elif d == 2:
if r1 == r2: # 같은 줄
if room[r1][(c1 + c2) // 2] != "X":
ok = 0
elif c1 == c2: # 같은 열
if room[(r1 + r2) // 2][c1] != "X":
ok = 0
elif room[r1][c2] != "X" or room[r2][c1] != "X": # 대각선
ok = 0
answer.append(ok)
return answer
room[r][c]: 대기실은 문자열 5개의 리스트라서, r번째 문자열의 c번째 글자가 (r, c) 칸이다.(r1, c1), (r2, c2) = people[i], people[j]: 두 튜플을 한 번에 풀어 담는다.for j in range(i + 1, …): 같은 쌍을 두 번 보지 않는다.
6단계 · 실행 추적
대기실 [“POOPX”, “OXPXP”, “PXXXO”, “OXXXO”, “OOOPP”]
| 쌍 | 거리 | 관계 | 판정 |
|---|---|---|---|
| (0,3)–(1,2) | 2 | 대각선, 모서리 (0,2) = O | 위반 |
| (4,3)–(4,4) | 1 | 바로 옆 | 위반 |
위반이 있으니 0이다.
7단계 · 복잡도와 흔한 실수
대기실마다 응시자 쌍 수만큼 보니, 대기실 하나에 최대 300쌍이다.
- 대각선에서 모서리 한 칸만 X여도 괜찮다고 본다. 두 칸 모두 X여야 막힌다.
- 거리 2 일직선에서 가운데 칸 대신 다른 칸을 본다.
- 한 대기실에서 위반을 찾은 뒤 결과를 1로 되돌린다. 한 번 0이면 그 대기실은 0이다.