문제

 

https://www.acmicpc.net/problem/9938

 

9938번: 방 청소

처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있

www.acmicpc.net

은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다.  서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.

은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대해서 다음과 같은 과정을 거친다.

  1. 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다.
  2. 서랍 Bi가 비어있다면, i번 술을 그 서랍에 보관한다.
  3. Ai에 들어있는 술을 다른 서랍으로 이동시킨다.(다른 서랍은 Ai에 들어있는 술이 들어갈 수 있는 서랍 중 하나이다) 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Ai에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
  4. Bi에 들어있는 술을 다른 서랍으로 이동시킨다. 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Bi에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
  5. 위의 과정이 모두 불가능한 경우에는 i번 술을 그 자리에서 마셔버린다. (은기는 전혀 취하지 않는다)

각각의 술에 대해서, 서랍에 보관할 수 있는지, 그 자리에서 마셔버리는지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ N, L ≤ 300,000)

다음 N개 줄에는 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ L, Ai ≠ Bi)

 

출력

1번 술부터 N번 술까지 순서대로 보관할 수 있는지, 그 자리에서 먹어야 하는지를 출력한다.

보관할 수 있는 경우에는 "LADICA"를, 먹어버려야 하는 경우에는 "SMECE"를 출력한다.

 

예제

입력 출력
9 10
1 2
3 4
5 6
7 8
9 10
2 3
1 5
8 2
7 9
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
 
 

문제풀이 코드

import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
N, L = map(int, input().split())
drawer = {x:x for x in range(1, L+1)}
have = {x:False for x in range(1, L+1)}
def find(x):
if x != drawer[x]:
drawer[x] = find(drawer[x])
return drawer[x]
def union(x, y):
rootX = find(x)
rootY = find(y)
drawer[rootX] = rootY
for i in range(N):
x, y = map(int, input().split())
if not have[x]:
have[x] = True
union(x, y)
print("LADICA")
elif not have[y]:
have[y] = True
union(y, x)
print("LADICA")
elif not have[find(x)]:
have[find(x)] = True
union(x, y)
print("LADICA")
elif not have[find(y)]:
have[find(y)] = True
union(y, x)
print("LADICA")
else:
print("SMECE")

풀이방식: 주어진 서랍과 서랍들의 부모서랍의 자리가 비어있는지 확인하는 문제이므로 union-find(응용)를 사용하여 문제 풀이

 

1. union과 find 함수를 생성

  - find 함수는 기존 템플릿과 동일하지만, union은 기존과 조금 달라진다.

  - union함수는 더 작은 값을 가지는게 아닌 y의 root값을 가져야 한다.

2. 문제를 4가지 경우로 분류할 수 있다.

  첫번째. 서랍 A가 비어있을 때

  두번째. 서랍 A의 부모서랍이 비어있을 때

  세번째. 서랍 B가 비어있을 때

  네번째. 서랍 B의 부모서랍이 비어있을 때

  ※ 부모서랍이 비었을 때를 확인하는 것은 현재 서랍이 비어있을 때 한칸씩 옮겨야 하기 때문이다.

3. union-find를 사용하기 위해 drawer와 서랍이 비어있는지 체크하기 위한 have를 생성한다.

4. 각 input을 받아오면서 2번에 해당하는 경우들을 체크한다.

5. 비어있는 서랍을 발견했다면 해당 서랍을 채워주고 union 함수를 호출하고 "LADICA"를 출력한다.

6. 아무 조건에 해당하지 않으면 서랍이 차있는 상태이기 때문에 "SMECE"를 출력

'Problem Solving > 백준' 카테고리의 다른 글

[백준] 12865.평범한 배낭  (0) 2023.03.02
[백준] 9251. LCS  (0) 2023.03.01
[백준] 2021.최소 환승 경로  (0) 2022.12.15
[백준] 1708.볼록 껍질  (0) 2022.11.27
[백준] 4181.Convex Hull  (0) 2022.11.27

+ Recent posts