💻 Problem
삼성 SW 역량 테스트 기출 - 2025 상반기 오전 1번 문제
💡 Approach
1. 아침 (morning)
모든 학생이 신앙심 1 얻기
but, 점심에 그룹원들이 각자 신앙심을 1씩 대표자에게 넘길 예정이기 때문에 이를 상쇄시킬 수 있다.
아침에 신앙심을 얻는 것(+1)과 점심에 대표자에게 신앙심을 넘기는 것(-1)이 상쇄돼서 아무 행동도 하지 않는다.
대신 점심에 대표자에게만 신앙심을 주면 된다.
2. 점심 (afternoon)
신봉 음식이 같으면서 연결되어 있는(인접한) 학생들끼리 그룹을 형성한다.
bfs로 학생들끼리 연결되어 있는지 확인한다.
그룹을 형성할 때(bfs) 대표자도 함께 찾는다.
그룹원들 중 신앙심이 가장 크면서 행 번호, 열 번호가 더 작은 학생이 대표자가 된다.
대표자에게는 그룹원 인원만큼의 신앙심을 준다.
찾은 대표자 정보는 저녁에 써야 하니 따로 저장해 준다.
3. 저녁 (evening)
각 그룹의 대표자 정보를 우선순위대로 정렬한다.
관심 음식이 적으면서 신앙심이 크고 행번호, 열 번호가 더 작은 순이다.
모든 그룹의 대표자가 신앙을 전파한다.
만약 대표자가 이미 전파를 당해 방어 상태라면 해당 대표자는 전파를 진행할 수 없다.
전파자는 (신앙심 % 4) 값에 따라 전파 방향을 결정한다.
전파자의 신앙심은 1만 남기고 (신앙심 - 1)이 간절함(X)이 된다.
간절함이 0이 되거나 격자 밖으로 나갈 때까지 계속해서 전파 방향으로 한 칸씩 이동하며 전파한다.
전파 대상이 전파자와 신봉 음식이 같으면 전파하지 않는다.
전파에는 강한 전파와 약한 전파가 있다.
전파 대상은 방어 상태가 된다. (방어 상태가 되면 해당 위치는 당일에 전파를 못하게 된다.)
- 강한 전파
- 전파자의 신봉 음식과 동일한 음식을 신봉하게 된다.
- 전파자의 간절함이 (전파 대상의 신앙심 + 1)만큼 깎인다.
- 전파 대상의 신앙심은 1 증가한다.
- 약한 전파
- 전파 대상은 기존 신봉 음식과 전파자의 신봉 음식을 모두 신봉하게 된다.
- 전파자의 간절함이 0이 되고 전파를 종료한다.
- 전파 대상의 신앙심이 간절함(X)만큼 증가한다.
4. 출력하기
해당 음식의 신봉자들의 신앙심 총합을 출력한다.
민트초코우유, 민트초코, 민트우유, 초코우유, 우유, 초코, 민트 순서로 출력해야 한다.
각 음식을 key로 한 딕셔너리를 만들어서 신앙심 총합을 구했다.
✏️ Solution
from collections import deque
def afternoon():
# 연결되어 있는 학생끼리 그룹 형성 (bfs)
visited = [[False] * N for _ in range(N)]
heads = [] # 각 그룹의 대표자
for i in range(N):
for j in range(N):
if not visited[i][j]:
head = bfs(visited, i, j)
heads.append(head)
return heads
def bfs(visited, y, x):
queue = deque([(y, x)])
visited[y][x] = True
cnt = 1 # 그룹원 수
hy, hx = y, x # 대표자
while queue:
y, x = queue.popleft()
for dy, dx in dyx:
ny = y + dy
nx = x + dx
# 같은 그룹이 되기 위한 조건:
# 배열 범위 안에 있으면서 방문한 적 없어야 하고 신봉 음식이 같아야 함
if (0 <= ny < N) and (0 <= nx < N) and not visited[ny][nx] and F[y][x] == F[ny][nx]:
visited[ny][nx] = True
queue.append((ny, nx))
cnt += 1
# 대표자 갱신
if (B[hy][hx], -hy, -hx) <= (B[ny][nx], -ny, -nx):
hy, hx = ny, nx
B[hy][hx] += cnt
return (hy, hx)
def evening(heads):
heads.sort(key=lambda x: (
len(F[x[0]][x[1]]), # 길이 오름차순
-B[x[0]][x[1]], # B 내림차순
x[0], # x[0] 오름차순
x[1] # x[1] 오름차순
))
defended = [[False] * N for _ in range(N)]
# 모든 그룹의 대표자들이 신앙 전파
for y, x in heads:
# 만약 대표자가 이미 전파를 당해 방어 상태라면 전파 불가
if defended[y][x]:
continue
X = B[y][x] - 1 # 간절함(X) = 신앙심 - 1
food = F[y][x] # 전파자의 신봉 음식
dy, dx = dyx[B[y][x] % 4] # 방향 결정
B[y][x] = 1 # 전파자 신앙심은 1만 남기기
while True:
y, x = y + dy, x + dx
# 간절함이 0이 되거나 격자 밖으로 나갈 때까지 전파
if not (0 <= y < N) or not (0 <= x < N) or X <= 0:
break
# 전파 대상이 전파자와 신봉 음식이 같으면 전파 하지 않음
if F[y][x] == food:
continue
# 전파 대상은 방어상태가 됨
defended[y][x] = True
# 강한 전파:
# 전파자의 신봉 음식과 동일한 음식을 신봉
# 전파자의 간절함이 (전파 대상의 신앙심 + 1)만큼 깎임
# 전파 대상 신앙심 1 증가
if X > B[y][x]:
F[y][x] = food
X -= B[y][x] + 1
B[y][x] += 1
# 약한 전파:
# 전파 대상은 기존 신봉 음식과 전파자의 신봉 음식을 모두 신봉하게 됨
# 전파자의 간절함이 0이 되고 전파 종료
# 전파 대상의 신앙심 X만큼 증가
else:
F[y][x] = ''.join(sorted(set(F[y][x] + food)))
B[y][x] += X
break
N, T = map(int, input().split()) # 배열 크기, 며칠
F = [list(input()) for _ in range(N)] # 신봉 음식
B = [list(map(int, input().split())) for _ in range(N)] # 신앙심
dyx = ((-1, 0), (1, 0), (0, -1), (0, 1)) # 상하좌우
for _ in range(T):
# morning:
# 모든 학생이 신앙심 1 얻기
# but, 점심에 그룹원들이 각자 신앙심을 1씩 대표자에게 넘길 것이기 때문에
# 아침과 점심의 신앙심이 상쇄됨 -> 점심에 대표자에게만 신앙심을 주면 됨
heads = afternoon()
evening(heads)
# 민트초코우유, 민트초코, 민트우유, 초코우유, 우유, 초코, 민트 순서
# 해당 음식의 신봉자들의 신앙심 총합 출력
total = { 'CMT': 0, 'CT':0, 'MT':0, 'CM': 0, 'M': 0, 'C': 0, 'T': 0 }
for i in range(N):
for j in range(N):
total[F[i][j]] += B[i][j]
print(*total.values())신봉 음식을 입력 그대로 알파벳 정보를 저장했지만, 비트 마스크를 활용하는 방법도 있다.