문제 요약
5개의 대기실이 주어진다.
각 대기실은 5 x 5 크기이며, 각 칸은 다음 중 하나다.
P: 응시자가 앉아 있는 자리
O: 빈 테이블
X: 파티션응시자들 사이의 맨해튼 거리가 2 이하이면 거리두기 위반이다.
단, 두 응시자 사이가 파티션으로 막혀 있다면 허용된다.
각 대기실별로 거리두기를 지키고 있으면 1, 위반이 있으면 0을 반환해야 한다.
핵심 아이디어
대기실 크기는 항상 5 x 5로 작다.
따라서 각 응시자 P 위치에서 BFS를 수행해 거리 2 이내에 다른 응시자가 있는지 확인하면 된다.
탐색 규칙은 다음과 같다.
- 시작 위치는 현재 응시자 위치다.
- 상하좌우로 이동한다.
- 이동 거리가 2를 넘으면 더 탐색하지 않는다.
- 파티션
X는 지나갈 수 없다. - 거리 2 이내에서 다른
P를 만나면 거리두기 위반이다.
왜 BFS를 사용할까?
거리두기 위반 여부는 맨해튼 거리 2 이내만 확인하면 된다.
BFS를 사용하면 현재 위치에서 가까운 칸부터 탐색할 수 있고, 이동 거리도 함께 관리하기 쉽다.
또한 파티션이 있는 경우 해당 방향으로 더 이상 탐색하지 않으면 되므로 조건 처리도 단순하다.
풀이 과정
1. 각 대기실 확인
places에는 5개의 대기실이 들어 있다.
각 대기실을 하나씩 확인하면서 거리두기를 지키면 1, 위반이면 0을 결과 배열에 넣는다.
2. 응시자 위치 찾기
대기실을 순회하며 P가 있는 위치를 찾는다.
각 P 위치에서 BFS를 수행한다.
3. 거리 2까지만 탐색
BFS 큐에는 다음 정보를 저장한다.
x좌표, y좌표, 현재 거리현재 거리가 2 이상이면 더 멀리 이동하지 않는다.
4. 다른 응시자를 만나면 위반
시작 위치가 아닌 다른 위치에서 P를 만나면 거리두기 위반이다.
이 경우 해당 대기실은 바로 0으로 처리한다.
Python 코드
from collections import deque
def solution(places):
answer = []
for place in places:
if is_valid_place(place):
answer.append(1)
else:
answer.append(0)
return answer
def is_valid_place(place):
for i in range(5):
for j in range(5):
if place[i][j] == "P":
if not bfs(place, i, j):
return False
return True
def bfs(place, start_x, start_y):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * 5 for _ in range(5)]
queue = deque()
visited[start_x][start_y] = True
queue.append((start_x, start_y, 0))
while queue:
x, y, distance = queue.popleft()
if distance >= 2:
continue
for dx, dy in directions:
nx = x + dx
ny = y + dy
next_distance = distance + 1
if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
continue
if visited[nx][ny]:
continue
if place[nx][ny] == "X":
continue
if place[nx][ny] == "P":
return False
visited[nx][ny] = True
queue.append((nx, ny, next_distance))
return True코드 설명
전체 대기실 순회
for place in places:각 대기실을 하나씩 확인한다.
is_valid_place가 True를 반환하면 거리두기를 지킨 것이므로 1을 넣는다.
응시자 위치에서 BFS 실행
if place[i][j] == "P":
if not bfs(place, i, j):
return False대기실 안의 모든 응시자 위치에서 거리 2 이내를 확인한다.
하나라도 위반이 발견되면 해당 대기실은 더 볼 필요 없이 False를 반환한다.
BFS 초기화
visited[start_x][start_y] = True
queue.append((start_x, start_y, 0))현재 응시자 위치에서 탐색을 시작한다.
거리 정보도 함께 큐에 저장한다.
거리 제한
if distance >= 2:
continue맨해튼 거리 2까지만 확인하면 된다.
현재 거리가 이미 2라면 그 위치에서 더 이동하지 않는다.
파티션 처리
if place[nx][ny] == "X":
continue파티션은 지나갈 수 없다.
따라서 파티션 뒤쪽에 있는 응시자는 현재 경로로는 영향을 주지 않는다.
위반 검사
if place[nx][ny] == "P":
return False거리 2 이내에서 다른 응시자를 만나면 거리두기 위반이다.
시간 복잡도
대기실은 5개이고, 각 대기실은 5 x 5로 고정이다.
각 응시자마다 거리 2까지만 BFS를 수행하므로 사실상 상수 시간이다.
일반화해서 대기실 한 변의 길이를 N이라고 하면 다음과 같이 볼 수 있다.
O(대기실 수 * N^2)공간 복잡도
BFS에서 방문 배열과 큐를 사용한다.
대기실 크기가 N x N이라면 공간 복잡도는 다음과 같다.
O(N^2)실제 문제에서는 5 x 5로 고정이므로 상수 공간에 가깝다.
정리
이 문제는 각 응시자 주변 거리 2까지만 확인하면 된다.
핵심은 다음과 같다.
P위치마다 BFS를 수행한다.- 파티션
X는 탐색하지 않는다. - 거리 2 이내에서 다른
P를 만나면 위반이다. - 하나라도 위반이 있으면 해당 대기실 결과는
0이다.
대기실 크기가 작기 때문에 BFS로 간단하고 안정적으로 해결할 수 있다.
