🔍 알고리즘 분류

• DP

💡 문제 풀이

단계가 4이상일 때 문자열이 만들어지는 규칙 ➡️ 3번째 전 문자열 + 2번째 전 문자열

• 1번 문제

  • 문자열의 길이를 담는 dp 배열 생성
  • dp[i] = dp[i-3] + dp[i-2]

• 2번 문제

  • 각 문자의 개수를 담는 cnt 배열 생성
  • 0-2까지 3번 반복하며 cnt[i][j] = cnt[i-3][j] + cnt[i-2][j]

• 3번 문제

  • 3단계까지 기저 문자열을 담는 base 배열 생성
  • find(idx, depth)함수로 재귀적으로 이분탐색
    • 왼쪽에서 온 경우: idx <= depth[i-3]
      • 오른쪽에서 온 경우: idx > depth[i-3]
      • depth가 3이하이면, base에서 찾아서 반환

📄 코드

t = int(input())
n = int(input())

dp = [0] * 101
cnt = [[0, 0, 0] for _ in range(101)]
base = ["", "X", "YZ", "ZX"]

dp[1] = 1
dp[2] = 2
dp[3] = 2
cnt[1] = [1, 0, 0]
cnt[2] = [0, 1, 1]
cnt[3] = [1, 0, 1]

# 이분탐색으로 기저문자 찾기
def find(idx, depth):
    if depth <= 3: # 기저문자 반환
        return base[depth][idx - 1]
    if dp[depth - 3] >= idx: # 왼쪽에서 옴
        return find(idx, depth - 3)
    else: # 오른쪽에서 옴
        return find(idx - dp[depth - 3], depth - 2)

for i in range(4, n + 1):
    dp[i] = dp[i - 3] + dp[i - 2]
    for j in range(3):
        cnt[i][j] = cnt[i - 3][j] + cnt[i - 2][j]

if t == 1:
    print(dp[n])
elif t == 2:
    k = int(input())
    print(find(k, n))
else:
    ch = input()
    print(cnt[n][ord(ch) - ord('X')])

• 시간복잡도: O(N)

참고: https://ongveloper.tistory.com/311

🔍 알고리즘 분류

• 투포인터

💡 문제 풀이

1. 배열 오름차순 정렬
2. 초기 포인터로 배열의 양 끝점 가리키고, 초기값(answer)을 두 지점의 합으로 설정
3. 두 값 더해주며 절댓값이 answer보다 작으면 갱신
4. 두 값의 합이 음수이면 start+1
5. 두 값의 합이 양수이면 end-1

📄 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arr.sort() # O(NlogN)

# 양 끝 지점 포인팅
start, end = 0, n - 1
ans_val = [arr[0], arr[1]]
answer = abs(arr[0] + arr[1])

# 투포인터 탐색: O(N)
while start < end:
    two_val = arr[start] + arr[end]
    if abs(two_val) < answer:
        answer = abs(arr[start] + arr[end])
        ans_val = [arr[start], arr[end]]
        if answer == 0:
            break
    # 합이 0보다 작으면 시작점 증가
    if two_val < 0:
        start += 1
    # 0보다 크면 끝점 감소
    else:
        end -= 1

# 오름차순 정렬 후 출력
ans_val.sort()
print(*ans_val)

• 시간복잡도: O(NlogN)

🔍 알고리즘 분류

• DFS

💡 문제 풀이

• 아래 두 가지 조건만 확인해주면서 DFS 진행하면 됨
  1. 양의 개수 > 늑대의 개수
  2. 부모 노드 방문 & 자식 노드 미방문

📄 코드

def solution(info, edges):
    answer = []
    visited = [False] * len(info)

    def dfs(sheep, wolf):
        if sheep > wolf:
            answer.append(sheep)
        else:
            return
        for p, c in edges:
            # 부모 노드 방문한 적 있으면서 자식 노드 처음 방문
            if visited[p] and not visited[c]:
                visited[c] = True
                if info[c] == 0:
                    dfs(sheep + 1, wolf)
                else:
                    dfs(sheep, wolf + 1)
                visited[c] = False # 백트래킹

    visited[0] = True
    dfs(1, 0)

    return max(answer)

• 시간복잡도: O(2^N)

🔍 알고리즘 분류

• 백트래킹

💡 문제 풀이

1차원 배열로도 구현 가능

1. row[x]=i는 (x행, i열)에 퀸이 놓여있다는 뜻
2. 유망성 판단은 현재 행인 x전까지 놓여있는 퀸 확인 1) 같은 열에 놓여있는지 확인 2) 대각선에 놓여있는지 확인: 행 차이==열 차이
3. 행이 n에 도달했을때 답 추가

📄 코드

n = int(input())

answer = 0
row = [0] * n

def is_promising(x):
    for i in range(x):
        if row[i] == row[x] or abs(i - x) == abs(row[i] - row[x]):
            return False
    return True

def dfs(x):
    global answer
    if x == n:
        answer += 1
        return
    for i in range(n):
        row[x] = i # x행 i열
        if is_promising(x):
            dfs(x + 1)

dfs(0)     
print(answer)

• 시간복잡도: O(N!)

🔍 알고리즘 분류

• 수학

💡 문제 풀이

• 아래와 같은 규칙으로 테두리가 생김
  • 끝 숫자를 보면 6, 12, 18, 24..씩 6의 배수만큼 차이가 증가

    1
    2-7
    8-19
    20-37
    38-61

• 끝 숫자가 n보다 작을 때까지 배열에 넣고 배열의 길이 출력

📄 코드

"""
1
2-7
8-19
20-37
38-61
"""

n = int(input())
edge = [1]
diff = 0
while edge[-1] < n:
    diff += 6
    edge.append(edge[-1] + diff)

print(len(edge))

• 시간복잡도: $O(\sqrt N)$

🔍 알고리즘 분류

• 수학

💡 문제 풀이

문제해석: 64, 32, 16, 8, 4, 2, 1 길이의 막대 몇 개를 가지고 만들 수 있는지

1. 현재 막대(n)이 x보다 크다면 반으로 나누기
2. 그렇지 않다면 x에서 n 빼주고 갯수 증가

📄 코드

x = int(input())

n = 64
answer = 0

while x > 0:
    if n > x:
        n //= 2
    else:
        x -= n
        answer += 1

print(answer)

• 시간복잡도: O(1)

🔍 알고리즘 분류

• 브루트포스

💡 문제 풀이

1. 8*8 크기의 체스판 슬라이싱
   • 시작점 범위는 행(0, n-7), 열(0, m-7)
   • 체스판 범위는 (현재행, 현재행+8), (현재열, 현재열+8)
2. 최소 변경 횟수 구하기
   • 두 패턴 만들기 -> (행+열)==짝수(W) 일때와 (행+열)==홀수(B) 일 때
   • 위 두 패턴별로 짝수/홀수마다 일치하지 않는 칸 개수 카운트
3. 두 패턴별 카운트한 것 중 최솟값을 정답으로 출력

📄 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(input().rstrip()) for _ in range(n)]
answer = int(1e9)

# 두 패턴 중 최소 변환 갯수를 선택
def calculate_min(arr):
    ans1, ans2 = 0, 0
    for i in range(8):
        for j in range(8):
            if (i + j) % 2 == 0: # 짝수
                if arr[i][j] != 'W':
                    ans1 += 1
                else:
                    ans2 += 1
            else: # 홀수
                if arr[i][j] != 'B':
                    ans1 += 1
                else:
                    ans2 += 1
    return min(ans1, ans2)

# 8*8크기의 체스판 슬라이싱
for i in range(n - 7):
    for j in range(m - 7):
        sliced = []
        for x in range(i, i + 8):
            row = ""
            for y in range(j, j + 8):
                row += board[x][y]
            sliced.append(row)
        answer = min(answer, calculate_min(sliced))

print(answer)

• 시간복잡도: O(NM)

🔍 알고리즘 분류

• 구현
• 브루트포스

💡 문제 풀이

테트리스를 뒤집을 수 없고 회전만 가능함에 주의❗️

1. 가능한 테트리스 모양 모두 shapes에 저장
2. 격자판 모두 탐색하며 테트리스 모양 놓기
   • 테트리스 셀 중 하나라도 격자판 범위 벗어나면 pass
   • 격자판 범위 내라면 값 계산후 최댓값 갱신

📄 코드

• Python

  import sys
  input = sys.stdin.readline
  

shapes = [ # 1 [(0,0), (0,1), (0,2), (0,3)], [(0,0), (1,0), (2,0), (3,0)],

# 2
[(0,0), (0,1), (1,1), (1,2)],
[(0,1), (1,0), (1,1), (2,0)],

# 3
[(0,1), (1,1), (2,0), (2,1)],
[(0,0), (0,1), (0,2), (1,2)],
[(0,0), (0,1), (1,0), (2,0)],
[(0,0), (1,0), (1,1), (1,2)],

# 4
[(0,0), (0,1), (0,2), (1,1)],
[(0,1), (1,0), (1,1), (2,1)],
[(0,1), (1,0), (1,1), (1,2)],
[(0,0), (1,0), (1,1), (2,0)]

# 5
[(0,0), (0,1), (1,0), (1,1)],

]

T = 1 while True: answer = -int(1e9) n = int(input()) if n == 0: break arr = [list(map(int, input().split())) for _ in range(n)] for i in range(n): for j in range(n): for s in shapes: total = 0 for dx, dy in s: # 범위 벗어나면 해당 모양 pass if not (0 <= i + dx < n and 0 <= j + dy < n): break total += arr[i + dx][j + dy] else: answer = max(answer, total)

print(f"{T}. {answer}")
T += 1

```

• 시간복잡도: O(N^)

🔍 알고리즘 분류

• 구현
• 시뮬레이션

💡 문제 풀이

1. 벽을 set에 양방향으로 저장하기
2. 바깥쪽 온도 1씩 감소할때 모서리 중복되지 않도록 주의하기

1. 격자 정보 받을 때 행, 열 인덱스 -1씩, 정보칸은 정보 따로 저장 후 0으로 변환

2. 히터 순회하며 온도 상승 1) queue를 이용해서 한 라인 진행될때마다 상승 온도 1씩 감소시키며 진행 2) 벽이 있으면 확산 중지

   • 마찬가지로 오, 왼, 위, 아래 각각 케이스 나눠서 확인

     3) 상승 온도가 0이면 확산 멈추기

3. 온도 조절

   • 새로운 2차원 배열에 변화값 저장 후 이후 한꺼번에 적용

4. 바깥쪽 온도 감소시키고 초콜릿 먹기

   • 모서리 중복 주의

5. 조사칸들 순회하며 k이상인지 조사 1) 모두 만족하면 성능테스트 끝내기 2) 아니면 계속 진행

6. 정답 출력

📄 코드

• Python

  import sys
  from collections import deque
  input = sys.stdin.readline
  

r, c, k = map(int, input().split()) arr = [] heaters = set() inspection = set()

dx = [0, 0, -1, 1] dy = [1, -1, 0, 0]

for i in range(r): row = list(map(int, input().split())) arr.append(row) for j in range(c): if row[j] == 5: inspection.add((i, j)) arr[i][j] = 0 # 정보 얻었으면 해당 칸 0으로 교체 elif row[j] != 5 and row[j] != 0: heaters.add((i, j, row[j] - 1)) arr[i][j] = 0 # 정보 얻었으면 해당 칸 0으로 교체

w = int(input()) walls = set() # 벽 정보 for _ in range(w): x, y, t = map(int, input().split()) x -= 1 y -= 1 if t == 0: # 양방향으로 저장 walls.add((x, y, x - 1, y)) walls.add((x - 1, y, x, y)) else: walls.add((x, y, x, y + 1)) walls.add((x, y + 1, x, y))

해당 칸이 격자판 범위 내인지 검사

def in_range(x, y): return 0 <= x < r and 0 <= y < c

두 칸 사이에 벽이 있는지 검사

def check_wall(x, y, nx, ny, dir): if dir == 0: # 오 if nx == x: # 바로 오 return (x, y, x, y + 1) in walls elif nx == x - 1: # 위쪽 오 return (x, y, x - 1, y) in walls or (x - 1, y, x - 1, y + 1) in walls elif nx == x + 1: # 아래쪽 오 return (x, y, x + 1, y) in walls or (x + 1, y, x + 1, y + 1) in walls elif dir == 1: # 왼 if nx == x: # 바로 왼 return (x, y, x, y - 1) in walls elif nx == x - 1: # 위쪽 왼 return (x, y, x - 1, y) in walls or (x - 1, y, x - 1, y - 1) in walls elif nx == x + 1: # 아래쪽 오 return (x, y, x + 1, y) in walls or (x + 1, y, x + 1, y - 1) in walls elif dir == 2: # 위 if ny == y: # 바로 위 return (x, y, x - 1, y) in walls elif ny == y - 1: # 왼쪽 위 return (x, y, x, y - 1) in walls or (x, y - 1, x - 1, y - 1) in walls elif ny == y + 1: # 오른쪽 위 return (x, y, x, y + 1) in walls or (x, y + 1, x - 1, y + 1) in walls elif dir == 3: # 아래 if ny == y: # 바로 아래 return (x, y, x + 1, y) in walls elif ny == y - 1: # 왼쪽 아래 return (x, y, x, y - 1) in walls or (x, y - 1, x + 1, y - 1) in walls elif ny == y + 1: # 오른쪽 아래 return (x, y, x, y + 1) in walls or (x, y + 1, x + 1, y + 1) in walls return False

온도 상승

def windows(x, y, dir): x = x + dx[dir] y = y + dy[dir] temper = 5 arr[x][y] += temper visited[x][y] = True q = deque([(x, y, temper - 1)]) while q: if temper == 0: break x, y, temper = q.popleft() if dir == 0: # 오 for i in [x - 1, x, x + 1]: if in_range(i, y + 1) and not visited[i][y + 1]: if check_wall(x, y, i, y + 1, dir) == False: # 벽 체크 arr[i][y + 1] += temper visited[i][y + 1] = True q.append((i, y + 1, temper - 1)) elif dir == 1: # 왼 for i in [x - 1, x, x + 1]: if in_range(i, y - 1) and not visited[i][y - 1]: if check_wall(x, y, i, y - 1, dir) == False: # 벽 체크 arr[i][y - 1] += temper visited[i][y - 1] = True q.append((i, y - 1, temper - 1)) elif dir == 2: # 위 for j in [y - 1, y, y + 1]: if in_range(x - 1, j) and not visited[x - 1][j]: if check_wall(x, y, x - 1, j, dir) == False: # 벽 체크 arr[x - 1][j] += temper visited[x - 1][j] = True q.append((x - 1, j, temper - 1)) elif dir == 3: # 아래 for j in [y - 1, y, y + 1]: if in_range(x + 1, j) and not visited[x + 1][j]: if check_wall(x, y, x + 1, j, dir) == False: # 벽 체크 arr[x + 1][j] += temper visited[x + 1][j] = True q.append((x + 1, j, temper - 1))

온도 조절

def control(): total_temper = [[0] * c for _ in range(r)] # 최종 온도 변화값 # 총 온도 변화 계산 for x in range(r): for y in range(c): for i in range(4): nx = x + dx[i] ny = y + dy[i] if in_range(nx, ny) and arr[x][y] > arr[nx][ny]: if check_wall(x, y, nx, ny, i) == False: diff = (arr[x][y] - arr[nx][ny]) // 4 total_temper[x][y] -= diff total_temper[nx][ny] += diff # 온도 적용 for i in range(r): for j in range(c): arr[i][j] += total_temper[i][j] if arr[i][j] < 0: arr[i][j] = 0

바깥쪽 온도 1씩 감소

def lower_side(): for i in [0, r - 1]: for j in range(c): if arr[i][j] - 1 >= 0: arr[i][j] -= 1 # 모서리 중복 처리 안되도록 주의!! for j in [0, c - 1]: for i in range(1, r - 1): if arr[i][j] - 1 >= 0: arr[i][j] -= 1

조사 칸들 k이상인지 검사

def check_inspection(): for x, y in inspection: if arr[x][y] < k: return False return True

chocolate = 0

성능테스트 하나씩 진행

while True: # 1. 히터마다 온도 상승시키기 for x, y, dir in heaters: # 한 히터에 대해서는 중복 방문x visited = [[False] * c for _ in range(r)] windows(x, y, dir)

# 2. 온도 조절
control()

# 3. 바깥쪽 온도 감소
lower_side()

# 4. 초콜릿 먹기
chocolate += 1

# 5. 조사
if check_inspection():
    break

# 100이 넘어가면 멈추기
if chocolate > 100:
    break

정답 출력

print(chocolate)

- 최적화 버전: 바람 확산 칸들 사전에 계산해서 딕셔너리에 저장
```python
import sys
from collections import deque
input = sys.stdin.readline

# 방향: 오른쪽, 왼쪽, 위, 아래
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

r, c, k = map(int, input().split())
arr = [[0] * c for _ in range(r)]
heaters = []
inspection = set()

for i in range(r):
    row = list(map(int, input().split()))
    for j in range(c):
        if row[j] == 5:
            inspection.add((i, j))
        elif row[j] != 0:
            heaters.append((i, j, row[j] - 1))  # (x, y, dir)

# 벽 정보 입력 및 세트화 (빠른 탐색 가능)
w = int(input())
walls = set()
for _ in range(w):
    x, y, t = map(int, input().split())
    x -= 1
    y -= 1
    if t == 0:  # 위쪽 벽
        walls.add((x, y, x - 1, y))
        walls.add((x - 1, y, x, y))
    else:  # 오른쪽 벽
        walls.add((x, y, x, y + 1))
        walls.add((x, y + 1, x, y))

def in_range(x, y):
    return 0 <= x < r and 0 <= y < c

def wall_blocked(x1, y1, x2, y2):
    return (x1, y1, x2, y2) in walls

# 히터 바람 영향 좌표 캐싱
heater_wind_map = dict()

def precompute_heater_wind():
    for x, y, dir in heaters:
        visited = [[False] * c for _ in range(r)]
        nx, ny = x + dx[dir], y + dy[dir]
        if not in_range(nx, ny):
            continue

        q = deque()
        q.append((nx, ny, 5))
        visited[nx][ny] = True
        temp_list = [(nx, ny, 5)]

        while q:
            cx, cy, val = q.popleft()
            if val == 1:
                continue

            if dir in (0, 1):  # 오 or 왼
                dlist = [(-1, dy[dir]), (0, dy[dir]), (1, dy[dir])]
            else:  # 위 or 아래
                dlist = [(dx[dir], -1), (dx[dir], 0), (dx[dir], 1)]

            for dx_, dy_ in dlist:
                nx, ny = cx + dx_, cy + dy_
                if not in_range(nx, ny) or visited[nx][ny]:
                    continue
                # 벽이 가로막는지 체크
                bx, by = cx, cy
                if wall_blocked(bx, by, bx + dx_, by) or wall_blocked(bx + dx_, by, bx + dx_, by + dy_):
                    continue
                visited[nx][ny] = True
                temp_list.append((nx, ny, val - 1))
                q.append((nx, ny, val - 1))

        heater_wind_map[(x, y, dir)] = temp_list

def apply_wind():
    for key in heater_wind_map:
        for x, y, val in heater_wind_map[key]:
            arr[x][y] += val

def control():
    delta = [[0]*c for _ in range(r)]
    for x in range(r):
        for y in range(c):
            for d in range(4):
                nx, ny = x + dx[d], y + dy[d]
                if not in_range(nx, ny):
                    continue
                if wall_blocked(x, y, nx, ny):
                    continue
                if arr[x][y] > arr[nx][ny]:
                    diff = (arr[x][y] - arr[nx][ny]) // 4
                    delta[x][y] -= diff
                    delta[nx][ny] += diff
    for i in range(r):
        for j in range(c):
            arr[i][j] += delta[i][j]

def lower_side():
    for i in [0, r-1]:
        for j in range(c):
            if arr[i][j] > 0:
                arr[i][j] -= 1
    for j in [0, c-1]:
        for i in range(1, r-1):
            if arr[i][j] > 0:
                arr[i][j] -= 1

def check_inspection():
    for x, y in inspection:
        if arr[x][y] < k:
            return False
    return True

# 사전 계산
precompute_heater_wind()

# 시뮬레이션 시작
choco = 0
while choco <= 100:
    apply_wind()       # 1. 히터 바람 영향 적용
    control()          # 2. 온도 조절
    lower_side()       # 3. 외곽 감소
    choco += 1         # 4. 초콜릿 먹기
    if check_inspection():  # 5. 검사
        break

print(choco)

• 시간복잡도: O(RC)

🔍 알고리즘 분류

• DP

💡 문제 풀이

1. dp 배열을 k+1만큼 생성 후 모두 최댓값으로 초기화
2. dp[0]=0으로 초기화
3. 가치를 1부터 탐색하며 이전 가치에서 동전을 하나 추가했을때 최솟값 찾아서 갱신

📄 코드

• Python

  import sys
  input = sys.stdin.readline
  

n, k = map(int, input().split()) coins = [] dp = [10001] * (k + 1) dp[0] = 0

for _ in range(n): coin = int(input()) coins.append(coin)

for i in range(1, k + 1): for coin in coins: if i - coin >= 0: dp[i] = min(dp[i], dp[i - coin] + 1)

if dp[k] == 10001: print(-1) else: print(dp[k])

```

• 시간복잡도: O(NK)

🔍 알고리즘 분류

• 누적합

💡 문제 풀이

1. 2차원 배열 범위를 (N+1)(N+1)로 늘리고 첫 행, 첫 열을 모두 0으로 채우기
2. 2차원 누적합 생성
3. 2차원 배열을 순회하며 시작점을 설정하고, K를 1부터 N까지 늘리면서 누적합 계산
4. 최댓값으로 정답 갱신

📄 코드

• Python

  import sys
  input = sys.stdin.readline
  

n = int(input())

첫 행, 첫 열 0으로 패딩주기

arr = [[0] * (n + 1)] for _ in range(n): arr.append([0]+list(map(int, input().split())))

누적합 생성

prefix_sum = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1): prefix_sum[i][1] = prefix_sum[i - 1][1] + arr[i][1]

for j in range(1, n + 1): prefix_sum[1][j] = prefix_sum[1][j - 1] + arr[1][j]

for i in range(2, n + 1): for j in range(2, n + 1): prefix_sum[i][j] = arr[i][j] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]

answer = -int(1e9)

for i in range(1, n + 1): for j in range(1, n + 1): # 정사각형 사이즈 1부터 늘리기 for k in range(1, n + 1): x1, y1, x2, y2 = i, j, i + k - 1, j + k - 1 # 범위 벗어나면 무시 if x2 > n or y2 > n: continue # 누적합 계산 total = prefix_sum[x2][y2] - prefix_sum[x1 - 1][y2] - prefix_sum[x2][y1 - 1] + prefix_sum[x1 - 1][y1 - 1] # 최댓값 갱신 answer = max(answer, total)

정답 출력

print(answer)

```

• 시간복잡도: O(N^3)

🔍 알고리즘 분류

• dfs
• 백트래킹
• 완탐

💡 문제 풀이

1. dfs/백트래킹으로 가능한 말의 조합 모두 생성
   • turn을 인자로 줘서 홀수면 X, 짝수면 O로 놓기
   • turn이 10이면 더 이상 놓을 수 없으므로 종료
   • 한 말로 3칸 연결되면 (2) 종료
2. 3칸 연결 확인
   • 가로 확인
   • 전치 행렬로 변환해서 세로 확인
   • 두 대각선 확인
3. set에 가능한 모든 조합 저장 후 입력 받을 때마다 set에 있는지 확인

📄 코드

• Python

  # 한 말이 3칸 이어지는지
  def check_line(c):
    # 가로 체크
    for row in board:
        if row.count(c) == 3:
            return True
    transform_board = [list(row) for row in zip(*board)]
    transform_board = tuple(map(tuple, transform_board))
    # 세로 체크
    for row in transform_board:
        if row.count(c) == 3:
            return True
    # 대각선 체크
    for i, j in zip(range(3), range(3)):
        if board[i][j] != c:
            break
    else:
        return True
    # 반대쪽 대각선 체크
    for i, j in zip(range(3), range(2, -1, -1)):
        if board[i][j] != c:
            break
    else:
        return True
  

가능한 모든 경우 탐색

def dfs(turn): # 3칸 연결 체크 if check_line('O') or check_line('X'): forms.add(tuple(map(tuple, board))) return # 꽉 채웠는지 체크 if turn == 10: forms.add(tuple(map(tuple, board))) return for i in range(3): for j in range(3): if board[i][j] == '.': board[i][j] = 'X' if turn % 2 == 1 else 'O' # 턴이 홀수일 땐 X, 짝수일 땐 O dfs(turn + 1) board[i][j] = '.'

board = [['.'] * 3 for _ in range(3)] forms = set() # 2차원 배열을 튜플로 변환 필요

dfs(1) # 첫 번째 턴부터 진행

while True: s = input() if s == "end": break

# 3*3 튜플 격자판 생성
arr = []
for i in range(0, 8, 3):
    arr.append(list(s[i:i+3]))
arr = tuple(map(tuple, arr))

# 가능한 조합에 없으면 invalid, 있으면 valid
if arr not in forms:
    print("invalid")
else:
    print("valid")

```

• 시간복잡도: O(9!)

🔍 알고리즘 분류

• 다익스트라

💡 문제 풀이

1. 노드에 도착하기 직전 노드를 저장하는 prev 배열 생성
2. 다익스트라 진행하면서 prev[현재노드] = 이전노드 저장
3. 다익스트라 진행 완료 후, 도착지점부터 출발지점까지 역추적하며 경로 생성

📄 코드

• Python

  import heapq
  

n = int(input()) m = int(input()) graph = [[] for _ in range(n + 1)] for _ in range(m): a, b, c = map(int, input().split()) graph[a].append((b, c)) start, end = map(int, input().split())

distance = [int(1e9)] * (n + 1) prev = [0] * (n + 1) # 이전 경로 기록

def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if dist > distance[now]: continue for i in graph[now]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost prev[i[0]] = now heapq.heappush(q, (cost, i[0]))

dijkstra(start) print(distance[end])

최단경로 역추적

path = [] cur = end while cur != start: path.append(cur) cur = prev[cur] path.append(start) path.reverse() print(len(path)) answer = " ".join(map(str,path)) print(answer) ```

🔍 알고리즘 분류

• 누적합

💡 문제 풀이

2차원 누적합 문제

1. arr와 누적합인 prefix_sum 2차원 배열의 첫 행, 첫 열을 모두 0으로 패딩을 넣어주는 것이 중요❗️
2. 누적합 생성 점화식
   • prefix_sum[i][j] = arr[i][j] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]
3. 구간별(x1, y1, x2, y2) 합 구하는 점화식
   • sum = prefix_sum[x2][y2] - prefix_sum[x1-1][y2] - prefix_sum[x2][y1-1] + prefix_sum[x1-1][y1-1]

📄 코드

• Python

  n, m = map(int, input().split())
  arr = [[0] * (n + 1)] # 첫 행, 첫 열을 모두 0으로 채우고 시작
  for _ in range(n):
    arr.append([0] + list(map(int, input().split())))
  

rectangles = [] for _ in range(m): a, b, c, d = map(int, input().split()) rectangles.append((a, b, c, d))

누적합 생성: 역시 첫 행, 첫 열은 모두 0으로

prefix_sum = [[0] * (n + 1) for _ in range(n + 1)]

가로 쭉 채우기

sum = 0 for i in range(1, n + 1): sum += arr[i][1] prefix_sum[i][1] = sum

세로 쭉 채우기

sum = 0 for j in range(1, n + 1): sum += arr[1][j] prefix_sum[1][j] = sum

누적합 생성

for i in range(1, n + 1): for j in range(1, n + 1): prefix_sum[i][j] = arr[i][j] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]

구간별 누적합 구하기

for x1, y1, x2, y2 in rectangles: ans = prefix_sum[x2][y2] - prefix_sum[x1-1][y2] - prefix_sum[x2][y1 - 1] + prefix_sum[x1 - 1][y1 - 1] print(ans) ```

🔍 알고리즘 분류

• 그래프

💡 문제 풀이

고려해야 할 문제 1. 같은 점을 다른 경로를 통해 돌아오는 것이 아니라 그냥 같은 길을 왕복해서 돌아올 수 있음 -> 간선을 따로 저장 2. 대각선이 교차할 때 -> 간선의 길이를 0.5로 설정하여 한 방향으로 두 번 나아가기

1. 방문한 점을 저장하는visited_nodes와 지나온 간선을 저장하는 visited_edges 생성
   • 점을 그냥 왕복해서 돌아올 수 있으므로 점만으로는 방의 개수를 판별할 수 없음
   • visited_edges는 무방향 간선 그래프로 설정
2. 대각선 교차를 고려하여 한 방향으로 나아가는 것을 총 2번 진행
3. 나아갈 점이 노드 셋에 있고, 나아갈 간선이 간선 셋에 없으면 정답에 1 추가
4. 노드 셋과 간선 셋에 새로운 점과 경로 추가

📄 코드

• Python

  def solution(arrows):
    answer = 0
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    x, y = 0, 0
    visited_nodes = set()
    visited_edges = set() # 같은 길 왕복하는 경우도 있을 수 있으므로 간선까지 고려
    visited_nodes.add((x, y))
  
    for d in arrows:
        for _ in range(2): # 대각선 교차 고려해서 0.5 길이씩 두 번
            nx = x + dx[d]
            ny = y + dy[d]
            # 새로운 경로로 노드 다시 방문한 경우
            if ((x, y), (nx, ny)) not in visited_edges:
                if (nx, ny) in visited_nodes:
                    answer += 1
            visited_nodes.add((nx, ny))
            # 무방향 간선
            visited_edges.add(((x, y), (nx, ny)))
            visited_edges.add(((nx, ny), (x, y)))
            x, y = nx, ny
  
    return answer

🔍 알고리즘 분류

• 구현

💡 문제 풀이

1. 참가자 이동
   • 상하좌우 순으로 이동했을 때 출구와의 맨해튼 거리가 짧아질 때에만 이동 수행
2. 출구와의 맨해튼 거리가 가장 짧은 참가자들 후보로 저장
3. 각 참가자들 순회하며 정사각형 생성
   • size, row, col 순으로 3중 for문 돌면서 정사각형 생성(인덱스 조정 잘 하기)
   • 참가자 1명 이상과 출구가 포함되는 즉시 정사각형 반환(사이즈 및 좌측상단과 우측하단의 좌표를)
4. 정사각형 회전 후 원래 배열에 적용
   • 참가자 위치와 출구 위치 또한 회전 후 적용
5. 이동한 사람들 개수를 정답에 추가
6. 위 과정 k번 동안 반복 후 정답 출력

📄 코드

• Python

  n, m, k = map(int, input().split())
  maze = [list(map(int, input().split())) for _ in range(n)]
  

참가자 위치 정보: [x, y, 출구까지의 거리, 인덱스]

people_pos = [[a - 1, b - 1, 100, idx] for idx, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(m)])]

격자 내 참가자 배치 상태

people_arr = [[[] for _ in range(n)] for _ in range(n)] for person in people_pos: x, y = person[0], person[1] people_arr[x][y].append(person[3])

출구 위치 (0-indexed)

ex, ey = map(lambda x: int(x) - 1, input().split())

def get_min_dist(sx, sy, ex, ey): """맨해튼 거리 반환""" return abs(sx - ex) + abs(sy - ey)

def move(x, y, ex, ey): """출구와 가까워지는 방향으로 1칸 이동""" for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: # 상하좌우 nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < n and maze[nx][ny] == 0: if get_min_dist(nx, ny, ex, ey) < get_min_dist(x, y, ex, ey): return nx, ny, get_min_dist(nx, ny, ex, ey) return x, y, get_min_dist(x, y, ex, ey)

def make_rectangle(dist, sx, sy, ex, ey): """출구와 참가자 1명 이상을 포함하는 가장 작은 정사각형 찾기""" dist += 1 # side = 거리 + 1 for sz in range(2, dist + 1): # 가능한 정사각형 크기 for x1 in range(n - sz + 1): for y1 in range(n - sz + 1): x2, y2 = x1 + sz - 1, y1 + sz - 1 if not (x1 <= ex <= x2 and y1 <= ey <= y2): continue for tx, ty, *_ in people_pos: if x1 <= tx <= x2 and y1 <= ty <= y2 and (tx != ex or ty != ey): return sz, x1, y1, x2, y2 return False

def rotate(side, sx, sy, endx, endy): """정사각형 회전 + 출구 위치 업데이트 + 사람 위치 업데이트""" global ex, ey

# 회전 임시 배열
rotated_maze = [[0] * side for _ in range(side)]
rotated_people = [[[] for _ in range(side)] for _ in range(side)]

# 출구가 정사각형 내에 있을 경우 회전
if sx <= ex <= sx + side - 1 and sy <= ey <= sy + side - 1:
    lx, ly = ex - sx, ey - sy
    ex, ey = sx + ly, sy + side - 1 - lx

# 회전 처리
for i in range(side):
    for j in range(side):
        gi, gj = sx + i, sy + j
        ri, rj = j, side - 1 - i
        rotated_maze[ri][rj] = max(maze[gi][gj] - 1, 0) if maze[gi][gj] else 0
        rotated_people[ri][rj] = people_arr[gi][gj][:]

# 회전 결과 적용
for i in range(side):
    for j in range(side):
        gi, gj = sx + i, sy + j
        maze[gi][gj] = rotated_maze[i][j]
        people_arr[gi][gj] = rotated_people[i][j][:]

# 참가자 위치 정보 업데이트
for i in range(n):
    for j in range(n):
        for person in people_arr[i][j]:
            people_pos[person] = [i, j, get_min_dist(i, j, ex, ey), person]

return ex, ey

=========================== 시뮬레이션 시작 ============================

answer = 0 people_cnt = m

for _ in range(k): if people_cnt == 0: break

# 참가자 이동 처리
next_people_arr = [[[] for _ in range(n)] for _ in range(n)]
for idx, (x, y, _, _) in enumerate(people_pos):
    if x == -1:
        continue
    nx, ny, dist = move(x, y, ex, ey)
    people_pos[idx][:3] = [nx, ny, dist]
    next_people_arr[nx][ny].append(idx)
    if (nx, ny) != (x, y):  # 실제 이동 시 카운트 증가
        answer += 1
    if nx == ex and ny == ey:  # 출구 도착
        people_pos[idx] = [-1, -1, 100, idx]
        people_cnt -= 1
        next_people_arr[nx][ny].remove(idx)

people_arr = next_people_arr

if people_cnt == 0:
    break

# 출구와 가장 가까운 사람 기준으로 정사각형 선택
candidate_people = sorted([p for p in people_pos if p[0] != -1], key=lambda x: x[2])
min_dist = candidate_people[0][2]
rects = []

for person in candidate_people:
    if person[2] != min_dist:
        break
    rect = make_rectangle(person[2], person[0], person[1], ex, ey)
    if rect:
        rects.append(rect)

if rects:
    rects.sort()  # 좌상단 기준 우선
    ex, ey = rotate(*rects[0])  # 회전

=========================== 결과 출력 ============================

print(answer) print(ex + 1, ey + 1) # 1-indexed 출력

```

시간: 54ms, 메모리: 16MB

🔍 알고리즘 분류

• 구현
• bfs

💡 문제 풀이

1. 공격자 선정
   • 배열 내 최솟값
   • 공격자가 될 수 있는 포탑들 후보 리스트candidate에 추가
   • candidate를 행과 열의 합, 열 순으로 오름차순 정렬
   • 공격 기록 뒤에서부터 돌며 만약 candidate 내에 있으면 공격자로 지정
   • 없으면 공격자는 candidate[0]
   • 패널티 적용
2. 공격 대상자 선정
   • 위와 동일
   • 조건 수정: 행과 열의 합, 열 순으로 내림차순, 공격 기록 앞에서부터
   • 조건 추가: 공격자가 아님
3. 최단 경로 찾기
   • 무조건 bfs로!! (dfs로 하면 시간초과)
   • 범위 벗어나면 반대쪽으로 넘어가게 모듈러 적용
4. 레이저 공격
   • 공격 관련 리스트에 추가
   • 경로에 있는 포탑들은 공격자 공격력의 반만큼, 공격 대상자는 공격력만큼 피해
   • 공격 받고 음수가 되면 0으로 치환
5. 포탑 공격
   • 공격 관련 리스트에 추가
   • 공격 대상자는 공격력만큼 피해
   • 주위 8칸에 있는 포탑들은 공격자 공격력의 반만큼 피해
     • 8칸 찾을 때에도 모듈러 적용
     • 공격자가 아닌지 확인 필수
   • 공격 받고 음수가 되면 0으로 치환
6. 포탑 정비 및 공격 기록에 공격자 추가
   • 공격 관련 리스트에 없는 포탑들 공격력+1
   • 공격 기록에 공격자 추가
7. 위 과정 k만큼 반복 후, 배열 내 최댓값 출력

📄 코드

• Python

  from collections import deque
  

n, m, k = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(n)] attacker_history = [] # 공격 기록 저장

공격자 찾기

def find_attacker(): min_bomb = 5000 tmp = [] row, col = 0, 0 for j in range(m): for i in range(n): if arr[i][j] != 0 and arr[i][j] <= min_bomb: min_bomb = arr[i][j] row, col = i, j tmp.append((i, j)) candidate = [bomb for bomb in tmp if arr[bomb[0]][bomb[1]] == min_bomb] candidate.sort(key=lambda x : (-(x[0]+x[1]), -x[1])) row, col = candidate[0] if len(candidate) > 1: # 공격한지 가장 최근 포탑 선정 for i in range(len(attacker_history) - 1, -1, -1): for j in range(len(candidate)): if attacker_history[i] == candidate[j]: row, col = candidate[j] break else: continue break arr[row][col] += n + m return row, col

공격 대상자 찾기

def find_victim(ax, ay): max_bomb = 0 tmp = [] row, col = 0, 0 for j in range(m - 1, -1, -1): for i in range(n - 1, -1, -1): if arr[i][j] != 0 and not (ax == i and ay == j) and arr[i][j] >= max_bomb: max_bomb = arr[i][j] row, col = i, j tmp.append((i, j)) candidate = [bomb for bomb in tmp if arr[bomb[0]][bomb[1]] == max_bomb] candidate.sort(key=lambda x : (x[0]+x[1], x[1]))

if len(candidate) > 1:
    row, col = candidate[0]
    # 일부만 공격기록 가지고 있을 때
    for candi in candidate:
        if candi not in attacker_history:
            return candi

    # 공격한지 가장 오래된 포탑 선정: 모두 공격 기록을 가지고 있을 때
    for i in range(len(attacker_history)):
        for j in range(len(candidate)):
            if attacker_history[i] == candidate[j]:
                row, col = candidate[j]
                break
        else:
            continue
        break

return row, col

우하좌상

dx = [0, 1, 0, -1] dy = [1, 0, -1, 0]

최단 경로 찾기: dfs 금지(시간초과)

def find_route_bfs(x, y, ex, ey): visited = [[False] * m for _ in range(n)] queue = deque() queue.append((x, y, [(x, y)])) visited[x][y] = True

while queue:
    cx, cy, path = queue.popleft()
    if cx == ex and cy == ey:
        return path
    for i in range(4):
        # 범위 벗어나면 반대쪽으로 가도록 모듈러 적용
        nx = (cx + dx[i]) % n
        ny = (cy + dy[i]) % m
        if not visited[nx][ny] and arr[nx][ny] > 0:
            visited[nx][ny] = True
            queue.append((nx, ny, path + [(nx, ny)]))

return []

for turn in range(k): # 남은 포탑이 1개면 중단 if sum([(row.count(0)) for row in arr]) == n * m - 1: break

# 공격자, 공격대상자 지정
ax, ay = find_attacker()
vx, vy = find_victim(ax, ay)

# 공격 기록 추가
if (ax, ay) in attacker_history:
    attacker_history.remove((ax, ay))
attacker_history.append((ax, ay)) 

min_route = find_route_bfs(ax, ay, vx, vy)
attacked = [(ax, ay)] # 공격과 관련 있는 포탑들

# 레이저 공격
if len(min_route) > 1:
    # 공격자인 첫 번째 원소 제거
    route = min_route[1:]
    for x, y in route:
        attacked.append((x, y))
        if x == vx and y == vy: # 공격 대상자 일때
            arr[x][y] -= arr[ax][ay]
            if arr[x][y] < 0:
                arr[x][y] = 0
        else:
            arr[x][y] -= arr[ax][ay] // 2 # 그외: 절반 만큼 피해
            if arr[x][y] < 0:
                arr[x][y] = 0

else: # 포탑 공격
    arr[vx][vy] -= arr[ax][ay]
    if arr[vx][vy] < 0:
        arr[vx][vy] = 0
    attacked.append((vx, vy))
    # 시계 방향
    ddx = [-1, -1, 0, 1, 1, 1, 0, -1]
    ddy = [0, 1, 1, 1, 0, -1, -1, -1]
    for i in range(8):
        nx = (vx + ddx[i]) % n
        ny = (vy + ddy[i]) % m
        if arr[nx][ny] != 0 and not (nx == ax and ny == ay): # 공격자가 아니고, 포탑이 있을때
            arr[nx][ny] -= arr[ax][ay] // 2
            if arr[nx][ny] < 0:
                arr[nx][ny] = 0
            attacked.append((nx, ny))

# 포탑 정비
for i in range(n):
    for j in range(m):
        if arr[i][j] != 0 and (i, j) not in attacked:
            arr[i][j] += 1

정답 출력: 배열 내 최댓값

print(max([max(row) for row in arr]))

```

시간: 252ms, 메모리: 23MB

🔍 알고리즘 분류

• 구현
• bfs

💡 문제 풀이

1. 명령 하나씩 수행하며 밀릴 예정인 기사들 반환
   • 현재 기사와 연결된 기사들 큐에 넣고 연쇄적으로 판단(bfs)
   • 어느 과정 중에라도 벽을 만난다면 빈 값으로 반환
2. 밀릴 예정인 기사들의 좌표 업데이트
   • 기사 배열에서 기존 자리 삭제 (0)
   • 이동한 자리 인덱스로 채우기
3. 업데이트된 기사들 다시 한 번 순회하며 데미지 계산
   • 각 기사들의 자리에 있는 함정 개수 카운트 = 데미지 배열에 업데이트
   • 동시에 함정 개수 만큼 체력 감소
4. 체력이 0인 기사가 있다면 기사 배열에서 제거(0)
5. 데미지 배열 순회하며 음수가 아닌 경우에만 정답에 추가

📄 코드

• Python

  from collections import deque
  

l, n, q = map(int, input().split()) fall_info = [list(map(int, input().split())) for _ in range(l)] # 벽, 함정 배열 arr = [[0] * l for _ in range(l)] # 기사 배열 people_pos = [[] for _ in range(n + 1)] # 각 기사 좌표 people_power = [0] # 각 기사 체력

기사 배열에 기사 표시

for idx in range(1, n + 1): r, c, h, w, k = map(int, input().split()) for i in range(r - 1, r - 1 + h): for j in range(c - 1, c - 1 + w): arr[i][j] = idx people_pos[idx].append([i, j]) people_power.append(k)

commands = [list(map(int, input().split())) for _ in range(q)] # 명령

상우하좌

dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1]

체스판 내에 있는지 확인

def in_range(x, y): return 0 <= x < l and 0 <= y < l

밀릴 예정인 기사들 반환 함수

def get_candidate(idx, direction): candidate = set() # 일직선상에 있는 밀릴 기사들 후보 candidate.add(idx) # 시작 기사는 무조건 추가

q = deque([idx])
# 현재 기사와 연결된 기사 모두 큐에 추가 (상하좌우에 따라 조건 다름)
while q:
    knight = q.popleft() # 현재 기사
    rows = set() # 시작 기사의 모든 행
    cols = set() # 시작 기사의 모든 열
    for x, y in people_pos[knight]:
        rows.add(x)
        cols.add(y)
    rows = list(rows)
    rows.sort()
    cols = list(cols)
    cols.sort()

    if direction == 0: # 상
        for col in cols:
            if not in_range(rows[0] - 1, col) or fall_info[rows[0] - 1][col] == 2: # 벽 만나면 모두 이동 불가
                return {}
            if in_range(rows[0] - 1, col) and arr[rows[0] - 1][col] > 0: # 기사가 맞닿아 있을 때
                candidate.add(arr[rows[0] - 1][col])
                q.append(arr[rows[0] - 1][col])
    elif direction == 1: # 우
        for row in rows:
            if not in_range(row, cols[-1] + 1) or fall_info[row][cols[-1] + 1] == 2: # 벽 만나면 모두 이동 불가
                return {}
            if in_range(row, cols[-1] + 1) and arr[row][cols[-1] + 1] > 0: # 기사가 맞닿아 있을 때
                candidate.add(arr[row][cols[-1] + 1])
                q.append(arr[row][cols[-1] + 1])
    elif direction == 2: # 하
        for col in cols:
            if not in_range(rows[-1] + 1, col) or fall_info[rows[-1] + 1][col] == 2: # 벽 만나면 모두 이동 불가
                return {}
            if in_range(rows[-1] + 1, col) and arr[rows[-1] + 1][col] > 0: # 기사가 맞닿아 있을 때
                candidate.add(arr[rows[-1] + 1][col])
                q.append(arr[rows[-1] + 1][col])
    elif direction == 3: # 좌
        for row in rows:
            if not in_range(row, cols[0] - 1) or fall_info[row][cols[0] - 1] == 2: # 벽 만나면 모두 이동 불가
                return {}
            if in_range(row, cols[0] - 1) and arr[row][cols[0] - 1] > 0: # 기사가 맞닿아 있을 때
                candidate.add(arr[row][cols[0] - 1])
                q.append(arr[row][cols[0] - 1])

return candidate

people_damaged = [0] * len(people_pos) # 각 기사가 받은 데미지

for idx, d in commands: # 사라진 기사일 경우 제외 if people_power[idx] == -1: continue

candidates = get_candidate(idx, d)

# 밀린 좌표 업데이트 및 기존 자리 삭제
for candi in candidates:
    updated_pos = []
    for x, y in people_pos[candi]:
        arr[x][y] = 0
        updated_pos.append([x + dx[d], y + dy[d]])
    people_pos[candi] = [row[:] for row in updated_pos]

# 밀린 좌표로 자리 표시
for candi in candidates:
    remain = people_power[candi] # 체력
    for x, y in people_pos[candi]:
        arr[x][y] = candi
        # 데미지 받을 때
        if fall_info[x][y] == 1: # 함정
            if candi != idx: # 명령 받은 기사 제외
                people_damaged[candi] += 1 # 데미지 추가
                people_power[candi] -= 1 # 체력 감소

# 체력 음수인 기사 제거
for candi in candidates:
    if people_power[candi] <= 0:
        for x, y in people_pos[candi]:
            arr[x][y] = 0
            people_pos[candi] = [-1, -1]
            people_power[candi] = -1
            people_damaged[candi] = -1

사라진 기사들 제외 데미지 총합 출력

answer = 0 for damage in people_damaged: if damage != -1: answer += damage print(answer)

```

시간: 67ms, 메모리: 18MB

🔍 알고리즘 분류

• 구현
• dfs

💡 문제 풀이

1. 탐색 진행 1)3X3 슬라이싱 후 90, 180, 270으로 회전

   • 총 27개의 경우의 수 발생

     2) 각 경우에서 유물가치가 최대가 되는 배열 구하기

   • 연결된 조각의 개수(dfs 또는 bfs로) 구해서 모두 더하기

   • 이때 사라진 조각들의 좌표 모두 저장하기 total_route

2. 유물 1차 획득 1) 사라진 조각들 자리 total_route 에 벽의 숫자 채우기 2) 벽의 숫자를 가리키는 인덱스는 전 과정에서 계속 보유하고 있어야함

3. 유물 연쇄 획득

   • 2번 과정과 동일, 더 이상 없을 때까지 반복

4. 각 턴 별 정답 출력

📄 코드

• Python

  k, m = map(int, input().split())
  arr = [list(map(int, input().split())) for _ in range(5)]
  nums = list(map(int, input().split()))
  # 북 남 동 서
  dx = [-1, 1, 0, 0]
  dy = [0, 0, 1, -1]
  # 행렬 회전 함수
  def rotate(grid, degree):
    result = [[0] * len(grid[0]) for _ in range(len(grid))]
    for i in range(3):
        for j in range(3):
            if degree == 1: # 90도
                result[j][3 - 1 - i] = grid[i][j]
            elif degree == 2: # 180도
                result[3 - 1 - i][3 - 1 - j] = grid[i][j]
            elif degree == 3: # 270도
                result[3 - 1 - j][i] = grid[i][j]
    return result
  

연결 요소 개수 세기

def dfs(grid, x, y, visited, path): visited[x][y] = True path.add((x, y)) cnt = 1 for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < 5 and 0 <= ny < 5: if grid[nx][ny] == grid[x][y] and not visited[nx][ny]: cnt += dfs(grid, nx, ny, visited, path) return cnt

유물 가치 계산

def get_max_val(grid): max_val = 0 visited = [[False] * 5 for _ in range(5)] total_route = [] # 모든 사라진 조각의 위치 저장 for i in range(5): for j in range(5): if not visited[i][j]: # 유물 삭제를 위해 기록 저장 path = set() val = dfs(grid, i, j, visited, path) if val >= 3: # 유물 완성 max_val += val total_route.extend(path) # 유물 삭제 for x, y in path: grid[x][y] = -1 return max_val, total_route

유물 사라진 곳 숫자 채우기

def fill(grid, route, idx): route.sort(key=lambda x: (x[1], -x[0])) # 작은 열, 큰 행 순으로 정렬 for i, j in route: grid[i][j] = nums[idx] idx += 1 return idx # 마지막 조각까지 채우고 그 다음 벽면 숫자의 인덱스 반환

flag = True # 탐사 진행 가능 여부 wall_idx = 0 # 현재 가리키고 있는 벽면 숫자의 인덱스 turn = 0 while turn < k and flag: flag = True answer = 0 # 각 턴마다의 유물 가치

# ==== 탐사 진행 시작 ====
# 중심점 지정
candidate = [] # 유물 가치 최대가 되는 배열 후보(유물가치, 배열, 회전각도, 회전중심열, 회전중심행)
max_value = 0 # 최대 유물 가치
for r in range(0, 3):
    for c in range(0, 3):
        # 배열 슬라이싱
        tmp = []
        for i in range(r, r + 3):
            row = []
            for j in range(c, c + 3):
                row.append(arr[i][j])
            tmp.append(row)

        # 3방향 회전
        rotated_tmp = []
        for degree in range(1, 4):
            rotated_tmp = rotate(tmp, degree)
            # 원래 배열에 합치기, 복사본으로
            copy_arr = [row[:] for row in arr]
            for rr in range(r, r + 3):
                for cc in range(c, c + 3):
                    copy_arr[rr][cc] = rotated_tmp[rr - r][cc - c]
            get_max_value, total_route = get_max_val(copy_arr)
            if get_max_value >= max_value:
                candidate.append([get_max_value, copy_arr, degree, c, r, total_route])


candidate.sort(key=lambda x: (-x[0], x[2], x[3], x[4]))
# 유물가치가 3개 이상 되는 경우가 없을 경우 탐사 중단
if candidate[0][0] < 3:
    flag = False
    break
selected_arr = candidate[0][1] # 유물가치가 최대가 되도록 회전한 배열
# ==== 탐사 진행 끝 ====

# ==== 유물 1차 획득 시작 ====
answer += candidate[0][0] # 사라진 조각 개수
total_route = candidate[0][5] # 사라진 조각들의 좌표

wall_idx = fill(selected_arr, total_route, wall_idx) # 다 채우고 다음 진행을 위해 벽면 인덱스 갱신
# ==== 유물 1차 획득 끝====

# ==== 유물 연쇄 획득 시작====
flag2 = True
while flag2:
    max_value, total_route = get_max_val(selected_arr)
    if max_value < 3:
        flag2 = False
        break
    answer += max_value

    wall_idx = fill(selected_arr, total_route, wall_idx) # 다 채우고 다음 진행을 위해 벽면 인덱스 갱신
# ==== 유물 연쇄 획득 끝====

# 정답 출력
print(answer, end=" ")

# 다음 진행을 위해 arr 갱신
arr = [row[:] for row in selected_arr]
turn += 1

```

시간: 144ms, 메모리: 21MB

🔍 알고리즘 분류

• 구현
• bfs

💡 문제 풀이

1. 시간의 벽 전개하기
2. 시간의 벽에서 면 간의 이동 구현하기 (인덱스 조정이 까다로움..)
3. 시간의 벽에서 bfs 수행
   • 이상현상 이동도 동시 수행
     • 지나온 turn을 set으로 관리하여 turn마다 단 한번만 실행되도록 해야 함
4. 바닥면에서 시간의 벽과의 통로 찾기
5. 위 지점을 시작점으로 bfs 수행
   • 예외처리: 통로가 탈출구일 때
   • 이상현상 이동도 동시 수행
6. 정답(탈출구 지점에서의 시간) 출력
   • 예외처리: 시간의 벽과 바닥면이 이동할 수 있는 통로가 없을 때 (이상현상 이동으로 인해)

📄 코드

• Python

  from collections import deque, defaultdict
  

n, m, f = map(int, input().split()) floor_map = [] # 바닥면(2차원) top_left = () # 시간의 벽 윗면 시작점 위치 current = () # 타임머신 초기 위치

바닥면 저장

for i in range(n): row = list(map(int, input().split())) floor_map.append(row) for j in range(len(row)): # 바닥에서 시간의 벽이 시작하는 위치 저장 if len(top_left) == 0 and row[j] == 3: top_left = (i, j)

time_map = [] # 시간의 벽(3차원) side = [] # 동 서 남 북 위

for i in range(1, 5 * m + 1): side.append(list(map(int, input().split()))) # 한 면 완성되면 시간의벽 에 저장 if i % m == 0: time_map.append(side) side = []

anomaly = defaultdict(list) # 이상현상 해시맵 for _ in range(f): r, c, d, v = map(int, input().split()) # v를 key, 나머지를 value로 갖도록 해시맵에 저장 anomaly[v].append([r, c, d]) # v에 대해 여러 이상현상이 있을 수 있으므로 list 사용

시간의 벽 전개

flat_map = [[-1] * 3 * m for _ in range(3 * m)]

동 = 왼쪽으로 90도 회전

tmp = [[0] * m for _ in range(m)] for i in range(m): for j in range(m): tmp[m - j - 1][i] = time_map[0][i][j] for i in range(m, 2 * m): for j in range(2 * m, 3 * m): flat_map[i][j] = tmp[i - m][j - 2 * m]

서 = 오른쪽으로 90도 회전

tmp = [[0] * m for _ in range(m)] for i in range(m): for j in range(m): tmp[j][m - 1 - i] = time_map[1][i][j] for i in range(m, 2 * m): for j in range(0, m): flat_map[i][j] = tmp[i - m][j]

남 = 그대로

for i in range(2 * m, 3 * m): for j in range(m, 2 * m): flat_map[i][j] = time_map[2][i - 2 * m][j - m]

북 = 180도 회전

tmp = [[0] * m for _ in range(m)] for i in range(m): for j in range(m): tmp[m - 1 - i][m - 1 - j] = time_map[3][i][j] for i in range(0, m): for j in range(m, 2 * m): flat_map[i][j] = tmp[i][j - m]

위

for i in range(m, 2 * m): for j in range(m, 2 * m): flat_map[i][j] = time_map[4][i - m][j - m] if flat_map[i][j] == 2: # 타임머신 초기 위치 저장 current = (i, j)

동서남북 중 어느 면에 있는지 확인하는 함수

def check_side(x, y): if m <= x < 2 * m and 2 * m <= y < 3 * m: # 동 return 0 elif m <= x < 2 * m and 0 <= y < m: # 서 return 1 elif 2 * m <= x < 3 * m and m <= y < 2 * m: # 남 return 2 elif 0 <= x < m and m <= y < 2 * m: # 북 return 3

동 서 남 북

dx = [0, 0, 1, -1] dy = [1, -1, 0, 0]

이상현상 이동한 turn 기록

visited_turn = set()

옆면 이동 함수

def move_side(x, y): nx, ny = -1, -1 if check_side(x, y) == 0: # 동 if x == m: # 동 -> 북 nx = (3 * m - y - 1) ny = 2 * m - 1 elif x == 2 * m - 1: # 동 -> 남 nx = 3 * m - 1 - (3 * m - y - 1) ny = 2 * m - 1 elif check_side(x, y) == 1: # 서 if x == m: # 서 -> 북 nx = y ny = m elif x == 2 * m - 1: # 서 -> 남 nx = (3 * m - y - 1) ny = m elif check_side(x, y) == 2: # 남 if y == 2 * m - 1: # 남 -> 동 nx = 2 * m - 1 ny = 3 * m - 1 - (3 * m - x - 1) elif y == m: # 남 -> 서 nx = 2 * m - 1 ny = (3 * m - x - 1) elif check_side(x, y) == 3: # 북 if y == 2 * m - 1: # 북 -> 동 nx = m ny = 3 * m - x - 1 elif y == m: # 북 -> 서 nx = m ny = x

return (nx, ny)

시간의 벽에서의 bfs

def bfs(x, y): time[x][y] = 0 q = deque([(x, y)]) while q: x, y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < 3 * m and 0 <= ny < 3 * m: # 이상현상 이동 turn = time[x][y] + 1 for v in anomaly: if (turn % v == 0): # 이상현상 이동이 해당 turn에 단 한 번만 이동하도록 if turn not in visited_turn: visited_turn.add(turn) for idx, val in enumerate(anomaly[v]): r, c, d = val floor_map[r][c] = 1 nr = r + dx[d] nc = c + dy[d] # 벽이 아니면 이상현상 이동 if 0 <= nr < n and 0 <= nc < n and floor_map[nr][nc] == 0: floor_map[nr][nc] = 1 anomaly[v][idx] = [nr, nc, d] # 이상현상 위치 갱신

            # 나아갈 수 있는 경우 시간 기록
            if time[nx][ny] > time[x][y] + 1: # 최단 시간 보장
                # 면 안에서의 이동
                if flat_map[nx][ny] == 0:
                    time[nx][ny] = time[x][y] + 1
                    q.append((nx, ny))
                # 면을 넘어갈 때
                elif flat_map[nx][ny] == -1: # 옆면 이동
                    nx, ny = move_side(x, y)

                    if flat_map[nx][ny] == 0:
                        if time[nx][ny] > time[x][y] + 1:
                            time[nx][ny] = time[x][y] + 1
                            q.append((nx, ny))

시간의 벽 내 시간 기록

time = [[int(1e9)] * 3 * m for _ in range(3 * m)] bfs(current[0], current[1])

바닥면 내 시간 기록

time_floor = [[int(1e9)] * n for _ in range(n)]

시간의 벽에서 바닥으로 이동할 수 있는 통로 찾기

path = () ith = -1 jth = -1 for i in range(top_left[0] - 1, top_left[0] + m + 1): ith += 1 for j in range(top_left[1] - 1, top_left[1] + m + 1): jth += 1 if floor_map[i][j] == 0: path = (i, j) if j == top_left[1] + m: # 동 time_floor[i][j] = time[m + ith - 1][3 * m - 1] + 1 elif j == top_left[1] - 1: # 서 time_floor[i][j] = time[m + ith - 1][0] + 1 elif i == top_left[0] + m: # 남 time_floor[i][j] = time[3 * m - 1][m + jth - 1] + 1 elif i == top_left[0] - 1: # 북 time_floor[i][j] = time[0][m + jth - 1] + 1 jth = -1

ans = -1

바닥면에서의 bfs

def bfs2(x, y): global ans # 엣지케이스: 탈출구가 연결 통로인 경우 if floor_map[x][y] == 4: ans = time_floor[x][y] return q = deque([(x, y)]) while q: x, y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < n and 0 <= ny < n: # 탈출구 도착 if floor_map[nx][ny] == 4: time_floor[nx][ny] = time_floor[x][y] + 1 ans = time_floor[nx][ny] return # 이상현상 이동 turn = time_floor[x][y] + 1 for v in anomaly: if (turn % v == 0): if turn not in visited_turn: visited_turn.add(turn) for idx, val in enumerate(anomaly[v]): r, c, d = val floor_map[r][c] = 1 nr = r + dx[d] nc = c + dy[d] if 0 <= nr < n and 0 <= nc < n and floor_map[nr][nc] == 0: floor_map[nr][nc] = 1 anomaly[v][idx] = [nr, nc, d]
# 나아갈 수 있는 경우 시간 기록 if floor_map[nx][ny] == 0 and time_floor[nx][ny] > time_floor[x][y] + 1: # 최단 시간 보장 time_floor[nx][ny] = time_floor[x][y] + 1 q.append((nx, ny))

이상현상 이동으로 바닥으로 이동할 수 없는 경우 제외

if len(path): bfs2(path[0], path[1])

정답 출력

print(ans)

```

시간: 51ms, 메모리: 17MB