문제 개요
기숙사에 번호가 0부터 n-1까지 매겨진 n개의 방이 있다고 가정해 봅시다. 각 방에 살고 있는 학생들은 다른 방으로 옮기고 싶어 하며, 여러 개의 이동(전송) 요청을 제출합니다. 단, 기숙사에는 빈자리가 하나도 남아서는 안 되며, 어떤 학생이 방을 옮기려면 반드시 다른 학생이 그 자리를 대신 차지해야만 요청이 처리됩니다.
이렇게 주어진 요청 목록에서 실제로 처리할 수 있는 요청이 최대 몇 개인지 구하는 것이 우리의 과제입니다.
예를 들어 입력이 n = 3, requests = [[0,2],[1,0],[2,1]]이라면 출력은 3이 됩니다. 즉, 세 개의 요청이 모두 처리될 수 있습니다.
- 0번 방의 학생이 2번 방으로 이동합니다.
- 1번 방의 학생이 0번 방으로 이동합니다.
- 2번 방의 학생이 1번 방으로 이동합니다.
모든 학생이 동시에 자리를 바꾸므로 어느 방도 비게 되지 않으며, 따라서 세 요청 전부 만족됩니다.
접근 방법
핵심 아이디어는 다음과 같습니다. 선택한 요청들을 모두 실행한 뒤에도 모든 방의 인원 변화량이 0이어야 한다는 점입니다. 즉, 어떤 방에서 나간 사람 수와 들어온 사람 수가 정확히 같아야 합니다.
이를 확인하기 위해 완전 탐색(brute force) 방식을 사용합니다. 요청 중에서 k개를 선택하는 모든 조합을 검사하되, k는 큰 값부터 작은 값 순서로 시도하여 처음으로 조건을 만족하는 k를 찾으면 그것이 곧 정답이 됩니다.
알고리즘 단계
- k를 요청 개수부터 1까지 1씩 감소시키면서 반복합니다.
- 0부터 요청 개수 범위에서 k개를 뽑는 모든 조합 c에 대해 다음을 수행합니다.
- 크기가 n이고 값이 모두 0인 배열 d를 생성합니다.
- 조합 c에 포함된 각 요청 i에 대해, 출발 방 인덱스의 값을 1 감소시키고 도착 방 인덱스의 값을 1 증가시킵니다.
- d의 모든 원소가 0이라면(즉, 어떤 방도 비거나 초과하지 않는다면) k를 반환합니다.
- 모든 경우를 검사해도 조건을 만족하는 조합이 없다면 0을 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
from itertools import combinations
def solve(n, requests):
for k in range(len(requests), 0, -1):
for c in combinations(range(len(requests)), k):
d = [0] * n
for i in c:
d[requests[i][0]] -= 1
d[requests[i][1]] += 1
if not any(d):
return k
return 0
print(solve(3, [[0,2],[1,0],[2,1]]))입력
3, [[0,2],[1,0],[2,1]]
출력
3
복잡도 분석
이 풀이는 모든 부분 집합을 검사하므로 시간 복잡도는 O(2^m × m)입니다. 여기서 m은 요청의 개수입니다. 요청 수가 많아지면 비효율적일 수 있지만, 문제의 제약 조건상 요청 개수가 작은 경우에는 충분히 실용적인 해법입니다.