1. BFS + 색칠: 인접한 노드를 0과 1로 번갈아 색칠하며 탐색
2. 충돌 검사: 같은 색의 노드가 인접하면 즉시 False 반환
3. 중복 방지: 큐에 넣을 때 바로 colors[c] 설정하여 중복 삽입 차단
4. 연결 요소 처리: 1~V까지 순회하며 끊어진 그래프도 모두 검사
5. 시간복잡도: O(V + E)로 최적화

from collections import defaultdict, deque
import sys

input = sys.stdin.readline

K = int(input())


def bfs():

    # 방문 체크와 색상 관리를 동시에 처리 가능(-1: 방문 안한 노드, 0/1: 색상)
    colors = [-1] * (V + 1)

    # 그래프의 전체 노드 순회해야 끊어진 그래프도 커버 가능함
    for i in range(1, V + 1):
        if colors[i] != -1:
            continue

        q = deque()

        q.append((i, 0))
        colors[i] = 0

        while q:
            node, color = q.popleft()

            other_color = -1
            if color == 0:
                other_color = 1
            else:
                other_color = 0

            for c in graph[node]:
                # 자식 노드가 부모 노드의 색상이 일치한다면 이분 그래프가 아니므로 False 리턴
                if colors[c] == color:
                    return False

                # 아직 방문 안한 자식 노드의 경우
                if colors[c] == -1:
                    q.append((c, other_color))
                    colors[c] = other_color

    return True


for test in range(K):
    V, E = map(int, input().split())

    graph = defaultdict(list)

    for e in range(E):
        u, v = map(int, input().split())

        graph[u].append(v)
        graph[v].append(u)

    if bfs():
        print("YES")
    else:
        print("NO")

• 재귀 구현 시, for문 안에서 재귀함수 호출할 때 값 여러개 리턴되는데 하나의 변수에 다 할당하는 실수 주의하기

• move_knight()에서 실수하지 않기
• 이미 다른 기사가 한번 밀었던 기사라면 패스(하나당 한 번만 밀어야 함)!! 면적이 w x h이므로 맞닿은 기사가 여러명일 수 있음 주의하기

from collections import defaultdict


L, N, Q = map(int, input().split())

maps = []

# 기사들의 위치를 표시할 맵
k_maps = [[0] * L for _ in range(L)]


for i in range(L):
    line = list(map(int, input().split()))

    maps.append(line)



positions = defaultdict(tuple)
bodys = defaultdict(tuple)
origin_hearts = defaultdict(int)
hearts = defaultdict(int)

# 죽은 기사 리스트
out_list = []


# 각 기사의 위치를 맵에 그리는 함수
def draw_body(r, c, num):

    h, w = bodys[num]

    for i in range(h):
        for j in range(w):

            if r + i >= L or c + j >= L:
                print(num, '이 맵 밖을 벗어남', r + i, c + j)
                return 0

            k_maps[r + i][c + j] = num


def count_damage(num):
    h, w = bodys[num]
    r, c = positions[num]

    cnt = 0

    for i in range(h):
        for j in range(w):
            # 해당 영역에 1(함정)이 있으면 누적
            if r + i >= L or c + j >= L:
                print(num, '이 맵 밖을 벗어남', r + i, c + j)
                return 0
            if maps[r + i][c + j] == 1:
                cnt += 1

    return cnt


for i in range(1, N + 1): # 기사 번호: 1 ~ N 번
    r, c, h, w, k = map(int, input().split())
    # 0부터 시작하도록 인덱스 맞춰주기!
    r -= 1
    c -= 1

    positions[i] = (r, c)
    bodys[i] = (h, w)
    hearts[i] = k
    origin_hearts[i] = k

    draw_body(r, c, i)



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



# 기사가 이동하는 방향에 따라 고려해야 하는 면의 좌표들을 반환
def get_part(r, c, num, d):
    part_list = []
    h, w = bodys[num]

    if d == 0:
        for i in range(w):
            part_list.append((r, c + i))
    elif d == 1:
        for i in range(h):
            part_list.append((r + i, c + w - 1))
    elif d == 2:
        for i in range(w):
            part_list.append((r + h - 1, c + i))
    elif d == 3:
        for i in range(h):
            part_list.append((r + i, c))

    return part_list


＃ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
def move_knight(n, direction):

    # 밀거나 밀려서 이동하는 기사 리스트
    move_knight_list = set()
    move_knight_list.add(n)


    def move_check(num, d):
        r, c = positions[num]

        parts = get_part(r, c, num, d)


        for r, c in parts:

            nr, nc = r + dx[d], c + dy[d]

            if nr < 0 or nr >= L or nc < 0 or nc >= L:
                return False


            # 이동할 곳에 하나라도 벽이 있다면
            if maps[nr][nc] == 2:
                return False


            # 이동할 곳에 다른 기사가 있다면 같은 방향으로 밀기
            if k_maps[nr][nc] > 0:

                another_num = k_maps[nr][nc]

                # 이미 다른 기사가 한번 밀었던 기사라면 패스(하나당 한 번만 밀어야 함)!! 맞닿은 기사가 여러명일 수 있음 주의!
                if another_num in move_knight_list:
                    continue
                # 같이 밀리는 기사 리스트 추가
                move_knight_list.add(another_num)

                # 재귀 호출
                # for문 안에 있으므로 여러개의 move_check 값이 리턴됨 주의!! 하나라도 False가 나오면 바로 return False 하기
                if not move_check(another_num, d):
                    return False

        return True


    is_possible = move_check(n, direction)


    # 같이 밀리는 기사 리스트와 움직임 가능 여부 리턴
    return list(move_knight_list), is_possible

＃ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－


# 명령
for i in range(Q):
    # move_num이 move_dir 방향으로 1칸 이동하라
    move_num, move_dir = map(int, input().split())


    # 사라진 기사에게 명령하면 패스
    if move_num in out_list:
        continue


    # 1) 기사 이동
    move_knight_list, is_possible = move_knight(move_num, move_dir)


    # 해당 방향으로 이동이 가능하다면, 각 기사의 좌표 이동시키기
    if is_possible:
        for num in move_knight_list:
            origin_r, origin_c = positions[num]

            nr, nc = origin_r + dx[move_dir], origin_c + dy[move_dir]

            positions[num] = (nr, nc)
    # 이동 불가능하다면 아무일 일어나지 않음
    else:
        continue

    # 이동 후, 밀려난 기사들 피해 누적하기
    for num in move_knight_list:
        # 명령받은 기사는 피해 제외
        if num == move_num:
            continue

        damage = count_damage(num)


        # 현재 체력 이상의 대미지 입을 시 사라짐
        if damage >= hearts[num]:
            out_list.append(num)
            del hearts[num]
            del positions[num]
            del origin_hearts[num]

        # 대미지보다 체력이 더 많은 경우
        else:
            hearts[num] -= damage

    # 이동한 기사들 포함 생존한 모든 기사들을 k_maps 초기화 후 위치 다시 그려주기
    k_maps = [[0] * L for _ in range(L)]

    for key, value in positions.items():

        draw_body(value[0], value[1], key)




# 살아남은 기사들의 시작 체력을 모두 더한 후, 최종 체력을 모두 더해서 빼주면 생존한 기사들의 총 데미지의 합이 됨
print(sum(origin_hearts.values()) - sum(hearts.values()))

• 항상 조건문 쓸 때는 발생가능한 모든 경우의 수를 elif로 틀을 다 만들어 둔 후, 각각의 경우의 수 안으로 들어가기

• while True 쓸 때는 어떤 조건에서 break 걸어야 하는지 꼼꼼히 체크
• dx dy를 두개 이상 만드는 경우, 다른 dx dy랑 헷갈리지 않게 주의
• nx ny가 여러개인 경우 다른 nx ny랑 헷갈리지 않게 주의
• nx를 ny로 ny를 nx로 오타나지 않게 주의
• 우선순위는 항상 꼼꼼하게 체크
• 코드는 돌아가는데 답이 틀리는 경우, 대부분 알고리즘은 맞는데 변수나 정의를 실수한 것이므로 처음부터 코드 꼼꼼히 따라가면서 실수한 부분 찾아보기
• 자잘한 세부 조건들 꼼꼼히 체크하기
• 반복되는 부분은 함수화 가능하면 하기. 그래야 실수가 덜 나는듯
• nx ny 만들 땐 항상 범위 체크 잊지말기(맵 밖으로 나가면 안됨)
• 딕셔너리 쓸 때: dict.keys(), dict.values(), dict.items(), del dict[삭제할 키]
• 제곱: x**2
• 기절해서 n턴 쉬게 해야할 때는 2차원 리스트에 각 턴별로 기절한 산타 리스트 관리하기! if turn >= 1 and idx in sleep_santas[turn - 1]: continue
• sort(key=lambda x: [x[0], x[1]])

from collections import defaultdict

N, M, P, C, D = map(int, input().split())

Rr, Rc = map(int, input().split())

Rr, Rc = Rr - 1, Rc - 1 # 0부터 시작하도록 인덱스 맞추기

santas_score = defaultdict(int) # 점수
maps = [[0] * N for _ in range(N)]
santas = defaultdict(tuple)

game_over_santas = []
sleep_santas = [[] for _ in range(M)]

for i in range(P):
    line = tuple(map(int, input().split()))
    # 좌표 0부터 시작하도록 인덱스 맞추기
    santas_score[line[0]] = 0
    santas[line[0]] = (line[1] - 1, line[2] - 1)
    maps[line[1] - 1][line[2] - 1] = line[0]


# 산타의 방향을 반대로 바꾸는 함수
def turn_dir(d):
    if 0 <= d <= 1:
        return d + 2
    else:
        return d - 2


# 루돌프 초기 위치 맵에 -1로 표시
maps[Rr][Rc] = -1


for turn in range(M):
    # 1) 루돌프 움직임 -------------------------------------------------------------------------------

    # 모든 산타들과 루돌프 간의 거리 계산
    santa_list = list(santas.values())

    santa_list.sort(key=lambda x: [-x[0], -x[1]]) # 우선순위 대로 sort

    min_dist = float('inf')
    target_santa = (-1, -1)

    for Sr, Sc in santa_list:

        dist = (Rr - Sr)**2 + (Rc - Sc)**2

        if dist < min_dist:
            min_dist = dist
            target_santa = (Sr, Sc)


    # 가장 우선순위가 높은 산타와 가까워지는 칸으로 루돌프 1칸 이동

    dx = [-1, -1, -1, 0, 1, 1, 1, 0]
    dy = [-1, 0, 1, 1, 1, 0, -1, -1]
    # 루돌프 주변 8칸 모두 거리 체크

    r_to_s_dist = float('inf')
    R_nx, R_ny = -1, -1
    R_dir = -1

    for i in range(8):

        nx, ny = Rr + dx[i], Rc + dy[i]

        if 0 <= nx < N and 0 <= ny < N:
            dist = (nx - target_santa[0])**2 + (ny - target_santa[1])**2
            if dist < r_to_s_dist:
                r_to_s_dist = dist
                R_nx, R_ny = nx, ny
                R_dir = i

    # (R_nx, R_ny)로 루돌프 1칸 이동

    # 만약 해당 칸에 산타 있을 시 충돌
    if maps[R_nx][R_ny] > 0:
        # 충돌
        santa_num = maps[R_nx][R_ny]
        santas_score[santa_num] += C

        # 루돌프 이동
        maps[Rr][Rc] = 0
        maps[R_nx][R_ny] = -1
        Rr, Rc = R_nx, R_ny

        # 산타는 루돌프가 이동해온 방향(R_dir)으로 C칸 밀려남
        S_nx, S_ny = R_nx + (dx[R_dir] * C), R_ny + (dy[R_dir] * C)

        # 이번 턴에 기절한 산타 추가
        sleep_santas[turn].append(santa_num)

        # 맵 밖으로 밀려나갔다면 탈락
        if S_nx < 0 or S_nx >= N or S_ny < 0 or S_ny >= N:
            game_over_santas.append(santa_num)
            del santas[santa_num]

        # 맵 안인데 산타가 있는 자리라면
        elif 0 <= S_nx < N and 0 <= S_ny < N and maps[S_nx][S_ny] > 0:

            # 상호작용
            A_nx, A_ny = S_nx, S_ny
            move_santa_num = santa_num

            while True:
                another_santa_num = maps[A_nx][A_ny]
                maps[A_nx][A_ny] = move_santa_num
                santas[move_santa_num] = (A_nx, A_ny)

                # 밀려난 산타는 1칸 해당 방향으로 밀려남
                A_nx, A_ny = A_nx + dx[R_dir], A_ny + dy[R_dir]


                # 맵 밖으로 밀려나갔다면 탈락
                if A_nx < 0 or A_nx >= N or A_ny < 0 or A_ny >= N:
                    game_over_santas.append(another_santa_num)
                    del santas[another_santa_num]

                    # 루프 종료!!!
                    break
                # 맵 안인데 산타가 있는 자리라면
                elif 0 <= A_nx < N and 0 <= A_ny < N and maps[A_nx][A_ny] > 0:
                    # 상호작용
                    move_santa_num = another_santa_num
                    continue
                # 맵 안인데 산타 없는 빈공간이라면
                elif 0 <= A_nx < N and 0 <= A_ny < N and maps[A_nx][A_ny] == 0:
                    maps[A_nx][A_ny] = another_santa_num
                    santas[another_santa_num] = (A_nx, A_ny)
                    break
        # 맵 안인데 산타 없는 빈공간이라면
        elif 0 <= S_nx < N and 0 <= S_ny < N and maps[S_nx][S_ny] == 0:
            maps[S_nx][S_ny] = santa_num
            santas[santa_num] = (S_nx, S_ny)

    else:
        # 루돌프 이동
        maps[Rr][Rc] = 0
        maps[R_nx][R_ny] = -1
        Rr, Rc = R_nx, R_ny



    # 2) 산타의 움직임 ------------------------------------------------------------------------------------------------------

    santa_list = list(santas.values())

    for idx in range(1, P + 1):

        if idx in sleep_santas[turn] or idx in game_over_santas:
            continue
        if turn >= 1 and idx in sleep_santas[turn - 1]:
            continue

        Sr, Sc = santas[idx]

        # 루돌프에게 가까워지는 방향 중 산타 없는 칸으로 1칸 이동

        dx_2 = [-1, 0, 1, 0] # 상 우 하 좌 우선순위
        dy_2 = [0, 1, 0, -1]

        min_dist = (Sr - Rr)**2 + (Sc - Rc)**2 # min_dist는 산타의 이동 전 좌표에서 루돌프까지의 거리로 초기화하기
        next_x, next_y = -1, -1
        santa_dir = -1

        for i in range(4):
            nx, ny = Sr + dx_2[i], Sc + dy_2[i] 

            # 맵 내부면서 산타 없는 칸이면
            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] <= 0:
                dist = (nx - Rr)**2 + (ny - Rc)**2

                # 기존 거리보다 작아지면서 최소값이라면 갱신
                if dist < min_dist:
                    min_dist = dist
                    next_x, next_y = nx, ny
                    santa_dir = i

        # 이동 불가라면 이동 X
        if next_x == -1 and next_y == -1:
            continue

        # 산타가 (next_x, next_y)로 이동
        maps[Sr][Sc] = 0

        # 만약 해당 칸에 루돌프가 있다면
        if maps[next_x][next_y] == -1:

            # 충돌
            santa_num = idx
            # 점수 얻기
            santas_score[santa_num] += D

            # 산타는 이동 방향의 반대 방향으로 D칸 밀려나기
            move_dir = turn_dir(santa_dir)

            S_nx, S_ny = next_x + (dx_2[move_dir] * D), next_y + (dy_2[move_dir] * D)


            # 이번 턴에 기절한 산타 추가
            sleep_santas[turn].append(santa_num)

            # 맵 밖으로 밀려나갔다면 탈락
            if S_nx < 0 or S_nx >= N or S_ny < 0 or S_ny >= N:
                game_over_santas.append(santa_num)
                del santas[santa_num]

            # 맵 안인데 산타가 있는 자리라면
            elif 0 <= S_nx < N and 0 <= S_ny < N and maps[S_nx][S_ny] > 0:

                # 상호작용
                A_nx, A_ny = S_nx, S_ny
                move_santa_num = santa_num

                while True:
                    another_santa_num = maps[A_nx][A_ny]
                    maps[A_nx][A_ny] = move_santa_num
                    santas[move_santa_num] = (A_nx, A_ny)

                    A_nx, A_ny = A_nx + dx_2[move_dir], A_ny + dy_2[move_dir] # 여기서 R_dir이랑 dx dy랑 혼동해서 씀!!!!

                    # 맵 밖으로 밀려나갔다면 탈락
                    if A_nx < 0 or A_nx >= N or A_ny < 0 or A_ny >= N:
                        game_over_santas.append(another_santa_num)
                        del santas[another_santa_num]

                        # 루프 종료!!!
                        break

                    # 맵 안인데 산타가 있는 자리라면
                    elif 0 <= A_nx < N and 0 <= A_ny < N and maps[A_nx][A_ny] > 0:
                        # 상호작용
                        move_santa_num = another_santa_num
                        continue

                    # 맵 안인데 산타 없는 빈공간이라면
                    elif 0 <= A_nx < N and 0 <= A_ny < N and maps[A_nx][A_ny] == 0:
                        maps[A_nx][A_ny] = another_santa_num
                        santas[another_santa_num] = (A_nx, A_ny)

                        break
            # 맵 안인데 산타 없는 빈공간이라면
            elif 0 <= S_nx < N and 0 <= S_ny < N and maps[S_nx][S_ny] == 0:
                maps[S_nx][S_ny] = santa_num
                santas[santa_num] = (S_nx, S_ny)

        # 해당 칸에 루돌프 없다면 그냥 이동
        else:
            maps[next_x][next_y] = idx
            santas[idx] = (next_x, next_y)


    # 만약 P명의 산타 모두 탈락 시 즉시 종료
    if len(game_over_santas) == P:
        break

    # 매 턴 끝나면 생존중인 산타 모두 +1점
    alive_santa = santas.keys()

    for s in alive_santa:
        santas_score[s] += 1



# 게임 종료 시 점수 출력

for i in range(1, P + 1):
    print(santas_score[i], end=" ")

• 꼭 알아야 할 코드:

1) 시계방향 90도 회전 output_arr = list(map(list, zip(*input_arr[::-1]))) 2) 180도 회전 output_arr = [a[::-1] for a in input_arr[::-1]] 3) 270도 회전 output_arr = [x[::-1] for x in list(map(list, zip(*input_arr[::-1])))[::-1]]

• 코드 실수 주의

  1) sort할 때 행 번호 큰 순인데 작은 순으로 잘못 봄! 조건 잘 보기 2) 탐사 진행하고 최대 유물인 경우 찾았는데 그 때의 회전한 맵을 현재 maps에 적용 안했음 3) BFS 할 때 같은 유적끼리 연결된 덩어리 카운트 하려면, group 리스트에 BFS 하면서 방문한 좌표를 모두 모아서 그 길이를 세어서 그걸로 연결된 조각 개수를 처리해야 함!

from collections import deque

K, M = map(int, input().split())
maps = []

for i in range(5):
    line = list(map(int, input().split()))
    maps.append(line)

wall = list(map(int, input().split()))

wall_idx = 0

# 중심 좌표(x, y) 기준으로 3x3 행렬의 좌표 구하는 dx, dy
dx = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 0, 1, -1, 0, 1]


def value_count(input_maps):

    dx_2 = [1, 0, 0, -1]
    dy_2 = [0, -1, 1, 0]

    visited = [[False] * 5 for _ in range(5)]
    total_cnt = 0
    total_group = []

    # 맵 전체 좌표 하나씩 돌면서 BFS 실행
    for j in range(5):
        for k in range(5):
            start_x, start_y = j, k

            # 이미 방문한 좌표라면 패스
            if visited[start_x][start_y]:
                continue


            # (start_x, start_y)에서 시작하는 BFS 수행
            visited[start_x][start_y] = True

            q = deque()
            q.append((start_x, start_y, input_maps[start_x][start_y]))

            group = [(start_x, start_y)]

            while q:
                x, y, num = q.popleft()


                for i in range(4):
                    nx, ny = x + dx_2[i], y + dy_2[i]

                    if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny] and input_maps[nx][ny] == num:

                        q.append((nx, ny, num))
                        group.append((nx, ny))
                        visited[nx][ny] = True

            # 찾은 유물 조각이 3개 이상 연결되어 있다면, 맵 안의 전체 유물에 추가
            if len(group) >= 3:

                total_cnt += len(group)
                total_group.extend(group)


    return total_cnt, total_group



def spin_arr(degree, input_arr):
    if degree == 0: # 90도 회전
        output_arr = list(map(list, zip(*input_arr[::-1])))
    elif degree == 1: # 180도 회전
        output_arr = [a[::-1] for a in input_arr[::-1]]
    elif degree == 2: # 270도 회전
        output_arr = [x[::-1] for x in list(map(list, zip(*input_arr[::-1])))[::-1]]

    return output_arr



def tamsa():

    max_val = -1
    max_group = []
    turned_maps = []

    # 가능한 회전 중심 좌표 : 열이 작은 순서, 행이 작은 순서대로 탐색!
    mid_list = [(1, 1), (2, 1), (3, 1), (1, 2), (2, 2), (3, 2), (1, 3), (2, 3), (3, 3)]

    # 각도가 가장 작은 순으로 탐색
    for d in range(3): # d = 0은 90도, d = 1은 180도, d = 2는 270도

        for x, y in mid_list:

            mini_3x3 = []

            idx = 0
            for i in range(3):
                line = []
                for j in range(3):
                    nx, ny = x + dx[idx], y + dy[idx]

                    line.append(maps[nx][ny])
                    idx += 1
                mini_3x3.append(line)


            # mini_3x3을 d도 돌리기
            spined_arr = spin_arr(d, mini_3x3)


            # spined_arr를 복사한 맵에 적용하기
            copy_maps = [row[:] for row in maps]

            idx = 0

            for i in range(3):
                for j in range(3):
                    nx, ny = x + dx[idx], y + dy[idx]

                    copy_maps[nx][ny] = spined_arr[i][j]
                    idx += 1


            # 복사한 맵에 spined_arr가 적용된 상태에서 유물 1차 획득 가능한 가치 카운트
            total_cnt, total_group = value_count(copy_maps)

            if total_cnt > max_val:
                max_val = total_cnt
                max_group = total_group
                turned_maps = [row[:] for row in copy_maps]

    return max_val, max_group, turned_maps



# 전체 K번 턴 진행
for turn in range(K):

    turn_val = 0

    max_val, max_group, turned_maps = tamsa()


    # 탐사 진행 과정에서 어떠한 유물도 획득 불가였다면 그 즉시 종료
    if max_val <= 0:
        break

    # 해당 턴의 유물 가치 누적  
    turn_val += max_val


    # 3x3 회전된 맵을 현재 맵에 적용
    maps = [row[:] for row in turned_maps]

    # 조각이 사라진 위치에 벽면 숫자를 순서대로 채워주기

    max_group.sort(lambda x: [x[1], -x[0]]) # 1) 열 작은순, 2) 행 큰순으로 정렬하기!!!!!


    for ax, ay in max_group:

        maps[ax][ay] = wall[wall_idx]
        wall_idx += 1


    # 유물 연쇄 획득

    total_cnt, total_group = value_count(maps)

    # 더 이상 조각이 3개 이상 연결되지 않아 유물이 될 수 없을 때까지 반복
    while total_cnt >= 3:

        # 해당 턴의 유물 가치 누적
        turn_val += total_cnt

        # 조각이 사라진 위치에 벽면 숫자를 순서대로 채워주기
        total_group.sort(lambda x: [x[1], -x[0]]) # 1) 열 작은순, 2) 행 큰순으로 정렬하기

        for ax, ay in total_group:
            maps[ax][ay] = wall[wall_idx]
            wall_idx += 1

        # 채운 후 다시 유물 카운트
        total_cnt, total_group = value_count(maps)


    # 이번 턴의 총 획득 유물 가치 출력
    print(turn_val, end=" ")

• 각 논에 우물 파는 비용을 “가상 정점에서 논으로 가는 간선”으로 초기 힙에 모두 삽입하기 (우물 비용 가장 싼 논에서 시작하는 걸로 하면 틀림! MST가 하나만 존재하는게 아니기 때문에)

• 힙에서 가장 싼 비용을 꺼내 방문하지 않은 논을 선택, 전체 비용 누적
• 선택된 논에서 다른 논으로 연결되는 파이프 비용을 힙에 추가하며 최소 비용 신장트리 만들기

• 우물 비용 vs 파이프 비용 중 자동으로 최소가 선택되도록(힙 이용) 만드는 것!

from collections import defaultdict
import heapq
import sys

input = sys.stdin.readline

N = int(input())
w_list = []
graph = defaultdict(list)

for i in range(N):
    W = int(input())
    w_list.append(W)

for i in range(N):
    line = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i].append((j, line[j]))


def prim():
    total_fee = 0
    heap = []
    for i in range(N):
        heapq.heappush(heap, (w_list[i], i))
    visited = [False] * N

    while heap:
        cost, node = heapq.heappop(heap)

        # pop한 후에도 방문체크 다시 해줘야 함(heap은 push된 순서대로 pop되지 않으므로)
        if visited[node]:
            continue

        visited[node] = True
        total_fee += cost

        # 현재 방문한 노드의 이웃 간선들 푸시하기
        for c, w in graph[node]:
            if not visited[c]:
                heapq.heappush(heap, (w, c))

    return total_fee


print(prim())

from collections import deque


R, C, K = map(int, input().split())



maps = [[0] * (C) for _ in range(R + 3)] # 골렘 시작위치를 처리하기 위해 3행 추가

def check_map(d, r, c):

    if d == 1: # 동쪽
        if 0 <= r - 1 and r + 1 < 3 + R and c + 2 < C and maps[r - 1][c + 1] == 0 and maps[r][c + 2] == 0 and maps[r + 1][c + 1] == 0:
            return True, r, c + 1
        return False, -1, -1
    elif d == 2: # 남쪽
        if 0 <= c - 1 and r + 2 < 3 + R and c + 1 < C and maps[r + 1][c + 1] == 0 and maps[r + 2][c] == 0 and maps[r + 1][c - 1] == 0:
            return True, r + 1, c
        return False, -1, -1
    elif d == 3: # 서쪽
        if 0 <= r - 1 and r + 1 < 3 + R and 0 <= c - 2 and maps[r - 1][c - 1] == 0 and maps[r][c - 2] == 0 and maps[r + 1][c - 1] == 0:
            return True, r, c - 1
        return False, -1, -1


def exit_clock(d):
    if d == 3:
        return 0
    return d + 1

def exit_anti_clock(d):
    if d == 0:
        return 3
    return d - 1

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

def draw_golem(di, i, r, c):

    # 골렘 중앙 표시
    maps[r][c] = i

    # 출구 표시
    nr, nc = r + dx[di], c + dy[di]
    maps[nr][nc] = -i

    # 골렘 몸 표시
    for j in range(4):
        if j == di:
            continue
        nr, nc = r + dx[j], c + dy[j]
        maps[nr][nc] = i


def move_fairy(x, y):

    num = maps[x][y]

    q = deque()
    visited = set()
    visited.add((x, y))
    q.append((x, y, num))

    max_row = -1

    while q:
        # num: 현재 머무르고 있는 골렘의 번호
        r, c, num = q.popleft()
        # 최대 행 갱신
        max_row = max(r, max_row)

        for i in range(4):
            nr, nc = r + dx[i], c + dy[i]

            if 3 <= nr < 3 + R and 0 <= nc < C and (nr, nc) not in visited and maps[nr][nc] != 0:

                # 현재 위치가 탈출구라면
                if maps[r][c] < 0:
                    # 다른 골렘으로 이동
                    if maps[nr][nc] != num:
                        q.append((nr, nc, abs(maps[nr][nc])))
                        visited.add((nr, nc))
                # 현재 있는 골렘 내부라면                
                if abs(maps[nr][nc]) == num:
                    q.append((nr, nc, num))
                    visited.add((nr, nc))

    return max_row




total_row_sum = 0

for i in range(1, K + 1):
    ci, di = map(int, input().split())

    # ci 에서 1 빼서 인덱스 시작 0으로 맞춰줘야 함 주의
    ci -= 1

    # 1) 골렘 중앙을 (1, ci)로 시작
    r, c = 1, ci

    # 골렘 이동 시작
    while True:
        # 1) 남쪽 확인
        is_okay, nr, nc = check_map(2, r, c)
        if is_okay:
            r, c = nr, nc
        else:
            # 2) 서쪽 + 남쪽 확인
            is_okay, nr, nc = check_map(3, r, c)
            is_moved = False

            if is_okay:
                # 남쪽도 확인
                is_okay, nnr, nnc = check_map(2, nr, nc)

                if is_okay:
                    r, c = nnr, nnc
                    # 출구 반시계방향으로 회전
                    di = exit_anti_clock(di)
                    is_moved = True

            # 2번도 실패 시
            # 3) 동쪽 + 남쪽 확인
            if not is_moved:

                is_okay, nr, nc = check_map(1, r, c)
                is_moved = False

                if is_okay:
                    # 남쪽도 확인
                    is_okay, nnr, nnc = check_map(2, nr, nc)

                    if is_okay:
                        r, c = nnr, nnc
                        # 출구 시계방향으로 회전
                        di = exit_clock(di)
                        is_moved = True

                # 더 이상 이동불가 종료
                if not is_moved:
                    break

    # 골렘 중심 위치 체크 - 골렘 일부분이 숲 바깥에 위치한다면 전체 리셋 후 다음 턴으로
    if r <= 3:
        maps = [[0] * (C) for _ in range(R + 3)] # 골렘 시작위치를 처리하기 위해 3행 추가
        continue


    # 골렘 이동 종료 시 맵에 골렘 위치 표시 (+i: 골렘, -i: 골렘 탈출구)

    draw_golem(di, i, r, c)

    # 정령 이동 BFS

    max_r = move_fairy(r, c)

    # 맵에 3행 추가 + 인덱스 0으로 진행했으므로 -3 + 1 = -2 더해줘야 함!
    max_r -= 2

    total_row_sum += max_r


print(total_row_sum)

• 경로는 1→V1→V2→N, 1→V2→V1→N 두 가지 경우만 고려하면 됨!

• 다익스트라는 dijkstra(1), dijkstra(V1), dijkstra(V2) 총 3번만 돌리면 구할 수 있음

from collections import defaultdict
import heapq

N, E = map(int, input().split())
graph = defaultdict(list)

for i in range(E):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


V1, V2 = map(int, input().split())


def dijkstra(start):
    dist = [float("inf")] * (N + 1)
    dist[start] = 0

    heap = []
    heapq.heappush(heap, (0, start))

    while heap:
        cost, node = heapq.heappop(heap)

        if dist[node] < cost:
            continue

        for v, w in graph[node]:
            new_cost = cost + w

            if new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(heap, (new_cost, v))

    return dist


dist_1 = dijkstra(1)

dist_V1 = dijkstra(V1)

dist_V2 = dijkstra(V2)

# 경우 1) 1 -> V1 -> V2 -> N 최단경로
total_dist_1 = dist_1[V1] + dist_V1[V2] + dist_V2[N]
# 경우 2) 1 -> V2 -> V1 -> N 최단경로
total_dist_2 = dist_1[V2] + dist_V2[V1] + dist_V1[N]

# 두 경우 중 더 최단경로 선택
answer = min(total_dist_1, total_dist_2)


# 만약 경로가 아예 존재하지 않는다면 -1 출력 (더한 경로들 중 하나라도 경로가 없어서 무한대가 더해졌다면 total 값은 무한대일 것이므로)
if answer == float("inf"):
    print(-1)
else:
    print(answer)

• get_exit()로 시간의 벽의 출구의 방향 및 좌표를 얻고, 출구가 있는 면엔 [0,1,1,...], 나머지 면엔 [1,1,...]를 M번째 행으로 추가하기

• warp(nr,nc,side)로 경계 이탈 시 면 이동 및 좌표 변환하기, 경계 이탈하지 않으면 그대로 (nr,nc,side) 반환하기(M번째 행 추가한 맵의 인덱스 체크 주의)
• 이상현상이 언제 해당 칸으로 확산되는지를 미리 계산해서 맵에 기록해두기
• 미지의 공간 BFS: 시작점 (s_start_r,s_start_c)에서 space_maps를 따라 확장하되, 해당 칸의 이상현상 확산시간 num에 대해 T+turn+1 < num일 때만 지나갈 수 있도록 구현하기(타임머신이 지나가기 직전에 이상현상이 먼저 확산됨 주의!)

from collections import deque

N, M, F = map(int, input().split())
space_maps = []

# 미지의 공간 평면도
for i in range(N):
    line = list(map(int, input().split()))
    for j in range(N):
        # 탈출구 -1로 표기 변경 (맵에 이상현상의 확산 시간을 양수로 표기할 것이므로)
        if line[j] == 4:
            line[j] = -1
    space_maps.append(line)

# 시간의 벽의 각 면의 2차원 맵
time_east = []
time_west = []
time_south = []
time_north = []
time_top = []

TOP, NORTH, EAST, SOUTH, WEST = 0, 1, 2, 3, 4

start_r, start_c = -1, -1

for j in range(M):
    line = list(map(int, input().split()))
    time_east.append(line)
for j in range(M):
    line = list(map(int, input().split()))
    time_west.append(line)
for j in range(M):
    line = list(map(int, input().split()))
    time_south.append(line)
for j in range(M):
    line = list(map(int, input().split()))
    time_north.append(line)
for j in range(M):
    line = list(map(int, input().split()))
    for l in range(M):
        # 타임머신 시작 좌표 저장
        if line[l] == 2:
            start_r, start_c = j, l

    time_top.append(line)

time_maps = []
time_maps.extend([time_top, time_north, time_east, time_south, time_west])


# 이상 현상 저장 리스트
strange = []

for i in range(F):
    line = list(map(int, input().split()))
    strange.append(line)


# 시간의 벽의 단 한칸의 출구의 방향 및 좌표 구하기
def get_exit():

    for i in range(N):
        for j in range(N):
            if space_maps[i][j] == 3:
                # 북쪽에 출구
                for k in range(M):
                    if 0 <= i - 1 < N and 0 <= j + k < N and space_maps[i - 1][j + k] == 0:
                        return 1, M - 1 - k, i - 1, j + k
                # 서쪽에 출구
                for k in range(M):
                    if 0 <= i + k < N and 0 <= j - 1 < N and space_maps[i + k][j - 1] == 0:
                        return 4, k, i + k, j - 1
                # 동쪽에 출구
                for k in range(M):
                    if 0 <= i + k < N and 0 <= j + M < N and space_maps[i + k][j + M] == 0:
                        return 2, M - 1 - k, i + k, j + M
                # 남쪽에 출구
                for k in range(M):
                    if 0 <= i + M < N and 0 <= j + k < N and space_maps[i + M][j + k] == 0:
                        return 3, k, i + M, j + k

# 시간의 벽 탈출한 후 시작점 좌표
s_start_r, s_start_c = -1, -1
exit_dir, k, s_start_r, s_start_c = get_exit()

others = [] # 출구를 가지지 않는 면들

# 시간의 벽의 출구(0)와 장애물인 곳(1)을 시간의 벽 맵에 표시해주기
line = []
for i in range(M):
    if i == k:
        line.append(0)
    else:
        line.append(1)

time_maps[exit_dir].append(line)


# 시간의 벽 출구가 없는 면들에는 1로 채워진 리스트 추가해주기(BFS에서 아래로 더 나아갈 수 없도록)
for i in range(1, 5):
    if i == exit_dir:
        continue

    line = []
    for j in range(M):
        line.append(1)

    time_maps[i].append(line)


# 0: top, 1: north, 2: east, 3: south, 4: west

dx = [0, 0, 1, -1] # 동, 서, 남, 북 순
dy = [1, -1, 0, 0]



# 시간의 벽에서의 탈출 경로 탐색 BFS
def bfs_time_space():

    visited = [set(), set(), set(), set(), set()]

    q = deque()
    q.append((start_r, start_c, 0, 0))
    visited[0].add((start_r, start_c))

    min_turn = -1

    # 시간의 벽의 다른 면으로 좌표 변환 처리 함수
    def warp(nr, nc, side):
        # warp 해당 사항 없다면 기존 그대로 리턴
        if side == 0 and 0 <= nr < M and 0 <= nc < M:
            return nr, nc, side
        elif 1 <= side <= 4 and 0 <= nr <= M and 0 <= nc < M:
            return nr, nc, side

        if side == TOP:
            if nr < 0:
                return 0, M - 1 - nc, NORTH
            elif nr > M - 1:
                return 0, nc, SOUTH
            elif nc < 0:
                return 0, nr, WEST
            elif nc > M - 1:
                return 0, M - 1 - nr, EAST


        elif side == NORTH:
            if nr < 0:
                return 0, M - 1 - nc, TOP
            elif nc < 0:
                return nr, M - 1, EAST
            elif nc > M - 1:
                return nr, 0, WEST

        elif side == EAST:
            if nr < 0:
                return M - 1 - nc, M - 1, TOP
            elif nc < 0:
                return nr, M - 1, SOUTH
            elif nc > M - 1:
                return nr, 0, NORTH

        elif side == SOUTH:
            if nr < 0:
                return M - 1, nc, TOP
            elif nc < 0:
                return nr, M - 1, WEST
            elif nc > M - 1:
                return nr, 0, EAST

        elif side == WEST:
            if nr < 0:
                return nc, 0, TOP
            elif nc < 0:
                return nr, M - 1, NORTH
            elif nc > M - 1:
                return nr, 0, SOUTH



    while q:

        r, c, side, turn = q.popleft()

        if r == M:
            min_turn = turn

            break


        for i in range(4):
            nr, nc = r + dx[i], c + dy[i]

            # 동,서,남,북 면에 있을 때 nr이 M 초과 시 맵 밖이므로 패스
            if 1 <= side <= 4 and nr > M:
                continue

            # 좌표 warp
            n_r, n_c, new_side = warp(nr, nc, side)

            if (n_r, n_c) not in visited[new_side] and time_maps[new_side][n_r][n_c] == 0:
                q.append((n_r, n_c, new_side, turn + 1))
                visited[new_side].add((n_r, n_c))


    # 탈출까지 최소 소요 시간 리턴
    return min_turn

T = bfs_time_space()



# 시간의 벽을 탈출한 후 미지의 공간의 탈출 경로 탐색 BFS
def bfs_space():

    q = deque()
    visited = set()
    q.append((s_start_r, s_start_c, 0))
    visited.add((s_start_r, s_start_c))

    time = -1

    while q:

        #print(q)
        r, c, turn = q.popleft()

        # 탈출구에 도착했다면
        if space_maps[r][c] == -1:
            time = turn
            break

        for i in range(4):
            nr, nc = r + dx[i], c + dy[i]

            if 0 <= nr < N and 0 <= nc < N and space_maps[nr][nc] != 1 and (nr, nc) not in visited:

                num = space_maps[nr][nc]

                # 그냥 빈공간이거나 탈출구라면 지나가기
                if num == 0 or num == -1:
                    q.append((nr, nc, turn + 1))
                    visited.add((nr, nc))

                # 미래에 이상현상 퍼질 공간이라면, 내가 지나갈 시간보다 퍼지는 시간이 이후라면
                elif T + turn + 1 < num:
                    q.append((nr, nc, turn + 1))
                    visited.add((nr, nc))

    return time



# 맵에 이상 현상 시작지점 표시
for s in strange:
    r, c, d, v = s[0], s[1], s[2], s[3]

    space_maps[r][c] = 1

# 맵에 각 이상현상이 확산되는 시간을 표기
for s in strange:
    r, c, d, v = s[0], s[1], s[2], s[3]

    nr, nc = r + dx[d], c + dy[d]
    turn = 1
    # 항상 다음 좌표 생성 시 맵 내부인지 인덱스 체크 꼭 하기!
    while 0 <= nr < N and 0 <= nc < N and space_maps[nr][nc] == 0:
        space_maps[nr][nc] = v * turn
        turn += 1
        nr, nc = nr + dx[d], nc + dy[d]

# 시간의 벽을 탈출할 수 없다면
if T == -1:
    print(-1)

# 아래 시간의 벽 탈출구에 이미 이상현상이 퍼졌다면 실패
elif space_maps[s_start_r][s_start_c] != 0 and T >= space_maps[s_start_r][s_start_c]:
    print(-1)
else:
    time = bfs_space()

    if time == -1:
        print(-1)
    else:
        print(T + time)

• 음수 가중치의 간선이 있을 때의 최단경로 문제 -> 벨만-포드 알고리즘

• 사이클 없는 최단경로는 최대 V-1개의 간선만 포함함
• 완화 연산: if dist[v] > dist[u] + w 거리가 더 짧아지면 갱신!
• V-1번 완화해서 모든 최단경로 구하기
• V-1번 후에도 최단경로가 또 갱신되면 시작점에서 도달 가능한 음수 사이클이 존재함을 의미함!

import sys

input = sys.stdin.readline

N, M = map(int, input().split())


bus_list = []

for i in range(M):
    a, b, c = map(int, input().split())

    bus_list.append((a, b, c))


# 음수 가중치의 간선이 존재하므로 벨만-포드 알고리즘 사용
def bellman_ford(start):

    dist = [float("inf")] * (N + 1)
    dist[start] = 0

    # V - 1 번 돌리기
    for _ in range(N - 1):
        updated = False

        for u, v, w in bus_list:

            if dist[u] != float("inf") and dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                updated = True

        if not updated:
            break

    # 전체 경로를 1번 다 돌고도, 추가 1라운드에서 최단거리 갱신이 또 일어난다면, 음수 사이클이 존재함을 의미
    negative_cycle = False
    for u, v, w in bus_list:

        if dist[u] != float("inf") and dist[v] > dist[u] + w:
            negative_cycle = True
            break

    return dist, negative_cycle


# 1번 도시에서 출발
dist, negative_cycle = bellman_ford(1)


# 음수 사이클이 존재하여 시간을 무한히 오래 전으로 되돌릴 수 있다면 -> 최단경로 보장이 안됨, -1 출력
if negative_cycle:
    print(-1)
else:
    for i in range(2, N + 1):
        # 해당 도시로 가는 경로가 없다면 -1 출력
        if dist[i] == float("inf"):
            print(-1)
        else:
            print(dist[i])

1) BFS 경로 복원으로 메두사가 공원까지 도로를 따라 갈 수 있는 최단경로 복원하기 2) 전사 뒤 영역을 메두사가 보지 못한다고 -1로 두면 안되는 이유: -1로 인해 볼 수 있는 전사(분홍 영역)를 탐색할 수 없게 되는 경우가 생김 -> 그래서 일단 전부 지나갈 수 있도록 해당 영역을 맵에서는 0으로 갱신하여 전사 뒤 영역도 탐색하게 한 다음, 0으로 갱신된(실제 메두사는 가려져서 못보는 영역) 좌표는 따로 cant_look_sight에 저장하여 medusa_sight(BFS로 탐색한 전체 영역) 에서 빼준 다음 최종 medusa_sight(메두사가 볼 수 있는 영역)를 리턴함 3) 맨해튼 거리로 거리 계산해야 함 -> dist = abs(nx - sr) + abs(ny - sc) 4) 전사 이동 시, 상하좌우 중 메두사와의 최소 거리인 방향으로 이동하는 게 아닌 "메두사와의 거리를 줄일 수 있는 방향" 인지도 꼭 체크해야 함! -> 기존 좌표의 메두사와의 거리(origin_dist)보다 더 작아지는 지도 체크 5) 방향 선택 기준의 우선순위는 각각 다르므로 주의하기 6) 돌이 된 전사는 이번 턴에서만 이동하지 못하는 것 -> 이번 턴 이동에서 돌 좌표만 제외하고 이동 7) 항상 인덱스, x, y 축 방향 주의 8) 조건 하나라도 놓치지 않기 -> 메두사가 이동한 좌표에 전사 있으면 즉시 없애기 9) 한 좌표 안에 전사 여러명 있을 수 있음 주의하기 10) 메두사 집에서 공원까지 가는 경로가 없을 수 있음 주의 11) 전사 이동 시 메두사 시야에 포함되지 않는 칸이여야 함 not in medusa_s

from collections import deque



N, M = map(int, input().split())

sr, sc, er, ec = map(int, input().split())

line = list(map(int, input().split()))

attackers = []

for i in range(0, 2 * M, 2):
    attackers.append((line[i], line[i + 1]))

# print(attackers)

maps = []

for i in range(N):
    line = list(map(int, input().split()))
    maps.append(line)

# print(maps)

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

# 메두사가 공원까지 도로를 따라 갈 수 있는 최단경로 구하는 함수
def search_shortest_path():

    visited = [[False] * N for _ in range(N)]
    parents = [[None] * N for _ in range(N)]
    visited[sr][sc] = True

    q = deque()
    q.append((sr, sc, 0))

    while q:
        x, y, level = q.popleft()

        # 공원에 도달했다면 종료
        if x == er and y == ec:
            break

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and maps[nx][ny] == 0:
                q.append((nx, ny, level + 1))
                visited[nx][ny] = True
                parents[nx][ny] = (x, y) # 부모 좌표 저장

    # 최단 경로 복원 ----------------------------------------
    path = [(er, ec)]
    cur_x, cur_y = er, ec

    while True:
        if parents[cur_x][cur_y] != None:
            cur_x, cur_y = parents[cur_x][cur_y]
            path.append((cur_x, cur_y))
        else:
            break

    path.reverse()

    return path


shortest_path = search_shortest_path()
medusa_idx = 0



def count_attacker(d):

    # 메두사가 볼 수 있는 영역 = 0, 못 보는 영역 = -1으로 표시
    avail_maps = [[-1] * N for _ in range(N)]


    if d == 0: # 상
        for i in range(1, sr + 1):
            nx = sr - i
            avail_maps[nx][sc] = 0
            # 메두사 기준 오른쪽
            for j in range(1, i + 1):
                ny = sc + j
                if 0 <= ny < N:
                    avail_maps[nx][ny] = 0
            # 메두사 기준 왼쪽
            for j in range(1, i + 1):
                ny = sc - j
                if 0 <= ny < N:
                    avail_maps[nx][ny] = 0

    elif d == 1: # 하
        for i in range(1, N - sr):
            nx = sr + i
            avail_maps[nx][sc] = 0
            # 메두사 기준 오른쪽
            for j in range(1, i + 1):
                ny = sc + j
                if 0 <= ny < N:
                    avail_maps[nx][ny] = 0
            # 메두사 기준 왼쪽
            for j in range(1, i + 1):
                ny = sc - j
                if 0 <= ny < N:
                    avail_maps[nx][ny] = 0

    elif d == 2: # 좌
        for i in range(1, sc + 1):
            ny = sc - i
            avail_maps[sr][ny] = 0
            # 메두사 기준 오른쪽
            for j in range(1, i + 1):
                nx = sr - j
                if 0 <= nx < N:
                    avail_maps[nx][ny] = 0
            # 메두사 기준 왼쪽
            for j in range(1, i + 1):
                nx = sr + j
                if 0 <= nx < N:
                    avail_maps[nx][ny] = 0

    elif d == 3: # 우
        for i in range(1, N - sc):
            ny = sc + i
            avail_maps[sr][ny] = 0
            # 메두사 기준 오른쪽
            for j in range(1, i + 1):
                nx = sr - j
                if 0 <= nx < N:
                    avail_maps[nx][ny] = 0
            # 메두사 기준 왼쪽
            for j in range(1, i + 1):
                nx = sr + j
                if 0 <= nx < N:
                    avail_maps[nx][ny] = 0



    # 메두사가 볼 수 있는 전사 수 카운트
    q = deque()
    q.append((sr, sc))

    visited = [[False] * N for _ in range(N)]

    # 맵의 각 좌표에 전사 몇명씩 위치하는지 표시하기
    for ax, ay in attackers:
        if avail_maps[ax][ay] >= 0: # 메두사가 볼 수 있는 영역(0)에만
            avail_maps[ax][ay] += 1 # 한 명당 + 1


    # 돌이 된 전사 수 카운트
    stone_cnt = 0

    # 돌이 된 전사 좌표 리스트 -> 이후 전사 이동에서 제외해야 하므로
    stones = []
    # 메두사가 볼 수 있는 영역
    medusa_sight = set()
    # 메두사가 전사에 의해 가려져 보지 못하는 좌표 저장
    cant_look_sight = set()

    # 디버깅을 위해 메두사는 맵에 -2로 표기
    avail_maps[sr][sc] = -2


    while q:
        x, y = q.popleft()

        for k in range(4):
            mx, my = x + dx[k], y + dy[k]

            # 메두사가 볼 수 있는 영역, 아직 방문하지 않은 영역인 경우
            if 0 <= mx < N and 0 <= my < N and avail_maps[mx][my] >= 0 and not visited[mx][my]:

                # 전사를 찾은 경우 (1 이상이면 전사 있는 것)
                if avail_maps[mx][my] >= 1:

                    # 해당 자리에 있는 돌이 될 전사 수 누적
                    stone_cnt += avail_maps[mx][my]
                    # 좌표도 누적
                    stones.append((mx, my))

                    # 전사의 뒤는 볼 수 없도록 맵에 0으로 처리하기
                    # 상
                    if d == 0:
                        # 메두사 위인 경우
                        if my == sc:
                            for i in range(1, mx + 1):
                                nx = mx - i
                                avail_maps[nx][my] = 0

                                # 메두사가 보지 못하는 영역을 따로 누적
                                cant_look_sight.add((nx, my))
                        # 메두사 기준 오른쪽인 경우
                        elif my > sc:
                            for i in range(1, mx + 1):
                                nx = mx - i
                                avail_maps[nx][my] = 0

                                cant_look_sight.add((nx, my))
                                # 메두사 기준 오른쪽
                                for j in range(1, i + 1):
                                    ny = my + j
                                    if 0 <= ny < N:
                                        avail_maps[nx][ny] = 0

                                        cant_look_sight.add((nx, ny))
                        # 메두사 기준 왼쪽인 경우
                        elif my < sc:
                            for i in range(1, mx + 1):
                                nx = mx - i
                                avail_maps[nx][my] = 0

                                cant_look_sight.add((nx, my))
                                # 메두사 기준 오른쪽
                                for j in range(1, i + 1):
                                    ny = my - j
                                    if 0 <= ny < N:
                                        avail_maps[nx][ny] = 0

                                        cant_look_sight.add((nx, ny))

                    # 하
                    elif d == 1:
                        # 메두사 아래인 경우
                        if my == sc:
                            for i in range(1, N - mx):
                                nx = mx + i
                                avail_maps[nx][my] = 0

                                cant_look_sight.add((nx, my))
                        # 메두사 기준 오른쪽인 경우
                        elif my > sc:
                            for i in range(1, N - mx):
                                nx = mx + i
                                avail_maps[nx][my] = 0

                                cant_look_sight.add((nx, my))
                                # 메두사 기준 오른쪽
                                for j in range(1, i + 1):
                                    ny = my + j
                                    if 0 <= ny < N:
                                        avail_maps[nx][ny] = 0

                                        cant_look_sight.add((nx, ny))
                        # 메두사 기준 왼쪽인 경우
                        elif my < sc:
                            for i in range(1, N - mx):
                                nx = mx + i
                                avail_maps[nx][my] = 0

                                cant_look_sight.add((nx, my))
                                # 메두사 기준 오른쪽
                                for j in range(1, i + 1):
                                    ny = my - j
                                    if 0 <= ny < N:
                                        avail_maps[nx][ny] = 0

                                        cant_look_sight.add((nx, ny))
                    # 좌
                    elif d == 2:
                        # 메두사 라인인 경우
                        if mx == sr:
                            for i in range(1, my + 1):
                                ny = my - i
                                avail_maps[mx][ny] = 0

                                cant_look_sight.add((mx, ny))
                        # 메두사 기준 위
                        elif mx < sr:
                            for i in range(1, my + 1):
                                ny = my - i
                                avail_maps[mx][ny] = 0

                                cant_look_sight.add((mx, ny))
                                # 메두사 기준 위
                                for j in range(1, i + 1):
                                    nx = mx - j
                                    if 0 <= nx < N:
                                        avail_maps[nx][ny] = 0

                                        cant_look_sight.add((nx, ny))
                        # 메두사 기준 아래
                        elif mx > sr:
                            for i in range(1, my + 1):
                                ny = my - i
                                avail_maps[mx][ny] = 0

                                cant_look_sight.add((mx, ny))

                                # 메두사 기준 아래
                                for j in range(1, i + 1):
                                    nx = mx + j
                                    if 0 <= nx < N:
                                        avail_maps[nx][ny] = 0

                                        cant_look_sight.add((nx, ny))

                    # 우
                    elif d == 3:
                        # 메두사 라인인 경우
                        if mx == sr:
                            for i in range(1, N - my):
                                ny = my + i
                                avail_maps[mx][ny] = 0

                                cant_look_sight.add((mx, ny))
                        # 메두사 기준 위
                        elif mx < sr:
                            for i in range(1, N - my):
                                ny = my + i
                                avail_maps[mx][ny] = 0

                                cant_look_sight.add((mx, ny))

                                # 메두사 기준 위
                                for j in range(1, i + 1):
                                    nx = mx - j
                                    if 0 <= nx < N:
                                        avail_maps[nx][ny] = 0

                                        cant_look_sight.add((nx, ny))
                        # 메두사 기준 아래
                        elif mx > sr:
                            for i in range(1, N - my):
                                ny = my + i
                                avail_maps[mx][ny] = 0

                                cant_look_sight.add((mx, ny))
                                # 메두사 기준 아래
                                for j in range(1, i + 1):
                                    nx = mx + j
                                    if 0 <= nx < N:
                                        avail_maps[nx][ny] = 0

                                        cant_look_sight.add((nx, ny))


                visited[mx][my] = True
                # 방문한 좌표는 메두사가 볼 수 있는 영역에 추가
                medusa_sight.add((mx, my))
                q.append((mx, my))

    # 전사에 가려져 볼 수 없는 좌표를 제외해서 진짜 메두사가 볼 수 있는 좌표만 리턴하기
    medusa_sight -= cant_look_sight


    return stone_cnt, stones, medusa_sight







while True:

    # 메두사의 집부터 공원까지 이어지는 도로가 없다면 -1 출력
    if len(shortest_path) == 1:
        print(-1)
        break

    # 1) 메두사의 이동
    medusa_idx += 1

    sr, sc = shortest_path[medusa_idx]

    # 메두사가 이동한 칸에 전사가 있을 경우 바로 사라짐 주의!
    while (sr, sc) in attackers:
        attackers.remove((sr, sc))

    # 메두사가 공원에 도착 시 종료
    if sr == er and sc == ec:
        print(0)
        break

    # 2) 메두사의 시선 -> 상 하 좌 우 순으로 볼 수 있는 전사 수 카운트
    max_cnt = -1
    medusa_d = -1
    stone_list = set()
    medusa_s = set()


    # 전사를 가장 많이 볼 수 있는 방향을 바라보기
    for i in range(4): # 0:상, 1:하, 2:좌, 3:우  우선순위
        c, stones, medusa_sight = count_attacker(i)
        if c > max_cnt:
            max_cnt = c
            medusa_d = i
            sto = list(stones)
            stone_list = set(sto)
            medusa_s = set(medusa_sight)


    # 3) 전사들의 이동 (돌 전사 제외하고)
    # 첫 번째 이동
    total_move = 0


    for idx, (ax, ay) in enumerate(attackers):
        # 돌이 되지 않았다면
        if (ax, ay) not in stone_list:

            # 이미 메두사 칸에 도달 시
            if ax == sr and ay == sc:
                continue

            origin_dist = abs(ax - sr) + abs(ay - sc)

            min_dist = float('inf')
            next_x, next_y = -1, -1

            # 상하좌우 순으로 확인
            for i in range(4):
                nx, ny = ax + dx[i], ay + dy[i]

                # 메두사 시야에 포함되지 않는 칸으로 이동 가능
                if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in medusa_s:
                    # 맨해튼 거리 공식으로 해야 함 주의!
                    dist = abs(nx - sr) + abs(ny - sc)

                    # 기존 메두사와의 거리보다 더 줄어드는 경우에만 움직이기 주의!
                    if dist < min_dist and dist < origin_dist:
                        min_dist = dist
                        next_x = nx
                        next_y = ny

            # 자리 갱신되었다면 반영
            if next_x != -1 and next_y != -1:
                attackers[idx] = (next_x, next_y)
                total_move += 1


    # 두 번째 이동   
    for idx, (ax, ay) in enumerate(attackers):
        # 돌이 되지 않았다면
        if (ax, ay) not in stone_list:

            # 이미 메두사 칸에 도달 시 패스
            if ax == sr and ay == sc:
                continue

            origin_dist = abs(ax - sr) + abs(ay - sc)

            min_dist = float('inf')
            next_x, next_y = -1, -1

            dx2 = [0, 0, -1, 1]
            dy2 = [-1, 1, 0, 0]

            # 좌우상하 순으로 확인
            for i in range(4):
                nx, ny = ax + dx2[i], ay + dy2[i]

                # 메두사 시야에 포함되지 않는 칸으로 이동 가능
                if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in medusa_s:
                    # 맨해튼 거리 공식으로 해야 함 주의!
                    dist = abs(nx - sr) + abs(ny - sc)

                    # 기존 메두사와의 거리보다 더 줄어드는 경우에만 움직이기 주의!
                    if dist < min_dist and dist < origin_dist:
                        min_dist = dist
                        next_x = nx
                        next_y = ny

            # 자리 갱신되었다면 반영
            if next_x != -1 and next_y != -1:
                attackers[idx] = (next_x, next_y)    
                total_move += 1  

    attacked_cnt = 0

    # 4) 전사의 공격
    for ax, ay in attackers:
        if ax == sr and ay == sc and (ax, ay) not in stone_list:
            attacked_cnt += 1


    # 죽은 전사 제외한 새로운 리스트 생성
    new_attackers = [x for x in attackers if x != (sr, sc)]
    attackers = new_attackers[:]


    print(total_move, max_cnt, attacked_cnt)

• permus = list(permus) -> 제너레이터를 list로 변환하면 모두 메모리에 올라가서 메모리 초과남 주의!! list 변환 없이 제너레이터 그대로 순회하면 됨!

• elem_cnt = abs(N - num) + i -> 두 수의 차이(+ or - 눌러야 하는 횟수) 계산 후 꼭 i 더하기! (해당 숫자를 만들기 위해 i번 버튼을 누르는 것이므로)

# 현재 채널 100번 -> N번으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는가?
from itertools import product

N = int(input())

M = int(input())

num_list = set()
num_list.update(["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"])
remain_list = []


if M != 0:
    broken_list = set(map(str, input().split()))

    # 0~9에서 입력받은 숫자들 제외하기
    remain_list = num_list - broken_list
# M이 0인 경우 리스트 입력 없음 주의
else:
    remain_list = num_list

# 사용 가능한 번호 리스트
remain_list = list(remain_list)
remain_list.sort()

min_cnt = 0

# [1] 100에서 +, -눌러서 이동하기
min_cnt = abs(100 - N)


# [2] 번호 새로 입력하고, +,- 눌러서 이동하기
N_str = str(N)
N_len = len(N_str)


# 1) N(목표 채널)의 길이가 2 이상인 경우
if N_len >= 2:

    # N_len - 1, N_len, N_len + 1 자릿수의 가능한 모든 수 구하기
    for i in range(N_len - 1, N_len + 2):

        # 현재 최소값보다 자리수 i 가 같거나 더 크다면 볼 필요 X (어차피 최소값이 될 수 없음)
        if i >= min_cnt:
            continue

        # 중복 순열!
        permus = product(remain_list, repeat=i)
        # permus = list(permus) # 제너레이터를 list로 변환하면 모두 메모리에 올라가서 메모리 초과남 주의!! list 변환 없이 제너레이터 그대로 순회하면 됨!

        for elem in permus:
            # 각 조합을 정수로 변환하기
            elem_list = list(elem)
            elem_list = "".join(elem_list)

            num = int(elem_list)

            # 두 수의 차이(+ or - 눌러야 하는 횟수) 계산 후 꼭 i 더하기! (해당 숫자를 만들기 위해 i번 버튼을 누르는 것이므로)
            elem_cnt = abs(N - num) + i

            # 최소값 갱신
            if elem_cnt < min_cnt:
                min_cnt = elem_cnt
# 2) N의 길이가 1인 경우
else:

    # N_len, N_len + 1 자릿수의 가능한 모든 수 구하기
    for i in range(N_len, N_len + 2):

        # 현재 최소값보다 자리수 i 가 같거나 더 크다면 볼 필요 X (어차피 최소값이 될 수 없음)
        if i >= min_cnt:
            continue

        # 중복 순열!
        permus = product(remain_list, repeat=i)
        # permus = list(permus) # 제너레이터를 list로 변환하면 모두 메모리에 올라가서 메모리 초과남 주의!! list 변환 없이 제너레이터 그대로 순회하면 됨!

        for elem in permus:
            # 각 조합을 정수로 변환하기
            elem_list = list(elem)
            elem_list = "".join(elem_list)

            num = int(elem_list)

            # 두 수의 차이(+ or - 눌러야 하는 횟수) 계산 후 꼭 i 더하기! (해당 숫자를 만들기 위해 i번 버튼을 누르는 것이므로)
            elem_cnt = abs(N - num) + i

            # 최소값 갱신
            if elem_cnt < min_cnt:
                min_cnt = elem_cnt

print(min_cnt)

• 빙산 녹이기: 매 해마다 ices 좌표 기준으로 사방의 바다 개수를 세고, 한꺼번에 높이를 줄여 동시 갱신하기

• 분리 여부 확인: bfs()로 빙산 덩어리 크기와 전체 빙산 개수를 비교해, 다 닿지 못하면 분리된 것으로 판정하기
• 시작 시 이미 분리된 경우 0 출력, 아니면 매 해 녹이고 분리되면 year_cnt 출력, 전부 녹으면 0 출력

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
maps = []
ices = []

for i in range(n):
    line = list(map(int, input().split()))
    maps.append(line)
    for j in range(len(line)):
        if line[j] != 0:
            ices.append((i, j, line[j]))


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


def melt_ice():

    # 이번 턴의 melt 후보리스트
    melt_list = []
    # 이번 턴에 녹고 남은 빙산 리스트
    new_ices = []

    # 현재 빙산 리스트 전체 순회
    for i in range(len(ices)):
        x, y, h = ices[i]

        water_cnt = 0

        # 빙산 위치의 상하좌우 체크하면서 물 갯수 카운트
        for j in range(4):
            nx, ny = x + dx[j], y + dy[j]

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 0:
                water_cnt += 1

        # 새로운 높이 계산
        new_h = h - water_cnt

        # 녹아서 물이 됐으면 melt 후보리스트에 추가 (바로 0으로 만들어버리면 안됨! 다른 빙산에 영향을 주므로 주의)
        if new_h <= 0:
            melt_list.append((x, y, h))

        # 아직 물이 되지는 않았다면 바로 갱신하기
        else:
            maps[x][y] = new_h
            new_ices.append((x, y, new_h))
            # ices[i] = (x, y, new_h)

    # 빙산을 모두 확인한 후 녹이기
    for x, y, h in melt_list:
        maps[x][y] = 0
        # ices.remove((x, y, h))

    return new_ices


def bfs():

    q = deque()
    visited = [[False] * m for _ in range(n)]

    group_cnt = 1  # 시작하는 빙산 하나 카운트

    if len(ices) > 0:
        start_x, start_y = ices[0][0], ices[0][1]
        q.append((start_x, start_y))

    # 시작 좌표 방문처리
    visited[start_x][start_y] = True

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if (
                0 <= nx < n
                and 0 <= ny < m
                and maps[nx][ny] != 0
                and not visited[nx][ny]
            ):
                group_cnt += 1
                visited[nx][ny] = True
                q.append((nx, ny))

    # 그룹이 2개 이상인 경우
    if group_cnt < len(ices):
        return False
    # 그룹이 1개인 경우
    return True


year_cnt = 0

while True:

    # 빙산이 1개 이상인 경우
    if len(ices) > 0:
        # 빙산 그룹이 2개 이상인 경우
        if not bfs():
            print(year_cnt)
            break
    # 빙산이 더 이상 없다면
    else:
        print("0")
        break

    # 빙산 녹이기
    ices = melt_ice()

    year_cnt += 1

# 1) 빙산 녹이기 : ices 리스트 돌면서 각 좌표의 maps값 갱신 및 ices 리스트 갱신

# 2) ices 리스트 중 한 좌표에서 시작해서 BFS 해서 한 번에 모든 빙산에 도달할 수 없다면 두 덩어리 이상임

• dist[v] = 시작점→v까지 경로 중 최소 간선값의 최댓값

• 시작점은 제약이 없으므로 dist[start] = float('inf') 로 두고 최대 힙(음수화)으로 탐색하기
• 힙에서 꺼낸 weight보다 작은 구버전 경로는 무시하기
• 이웃 탐색 시 new_w = min(weight, w)로 병목(최소 간선값) 갱신, 기존보다 크면(최댓값 찾아야 하므로) dist와 힙 갱신하기

from collections import defaultdict
import heapq
import sys

input = sys.stdin.readline


N, M = map(int, input().split())

graph = defaultdict(list)

for i in range(M):
    line = list(map(int, input().split()))
    a, b, c = line[0], line[1], line[2]
    graph[a].append((b, c))
    graph[b].append((a, c))

f1, f2 = map(int, input().split())


# 지금까지의 경로 가중치 중 최소 간선값을 최대화하기
def max_dijkstra(start):
    # dist[v]: 시작점에서 v까지 갈 수 있는 경로들 중 최소 간선값의 최댓값
    dist = [-float("inf")] * (N + 1)
    # 출발점은 아직 최소값 제한이 없으므로 무한대로 초기화 해야함 주의!! (0으로 설정하면 모든 dist가 항상 0 됨)
    dist[start] = float("inf")

    heap = []
    heapq.heappush(heap, (-dist[start], start))  # 최대 힙 구현을 위해 -붙여서 넣기!

    while heap:
        weight, node = heapq.heappop(heap)
        weight = -weight  # 음수를 양수로 바꿔줘야 함 주의!!

        # 도착지에 도착 시 종료
        if node == f2:
            break

        # 구버전은 무시하기(현재 값보다 더 작은 경로라면)
        if weight < dist[node]:
            continue

        for c, w in graph[node]:
            new_w = min(weight, w)  # 현재까지의 간선들 중 최소 간선값
            # 기존의 최소 간선값의 최댓값(dist[c])보다 현재 값이 더 크면 갱신
            if new_w > dist[c]:
                dist[c] = new_w
                # 힙에 weight 넣을 땐 음수로 넣기!(최대 힙)
                heapq.heappush(heap, (-new_w, c))

    # 시작점(f1)에서 도착지(f2)까지 갈 수 있는 경로 중 최소 간선값의 최댓값 리턴
    return dist[f2]


print(max_dijkstra(f1))

from collections import defaultdict
import heapq, sys

# 입력이 많은 경우 최적화해주기
input = sys.stdin.readline

V, E = map(int, input().split())

K = int(input())
graph = defaultdict(list)

for i in range(E):
    line = list(map(int, input().split()))
    u, v, w = line[0], line[1], line[2]
    graph[u].append((v, w))


def dijkstra(start):
    dist = [float("inf")] * (V + 1)
    dist[start] = 0
    heap = []

    heapq.heappush(heap, (0, start))

    while heap:
        cost, node = heapq.heappop(heap)

        if dist[node] < cost:
            continue

        for c, w in graph[node]:
            new_cost = cost + w

            if new_cost < dist[c]:
                dist[c] = new_cost
                heapq.heappush(heap, (new_cost, c))

    return dist


dist = dijkstra(K)

for i in range(1, V + 1):
    # 경로 존재하지 않는 경우(초기화값이 그대로인 경우)
    if dist[i] == float("inf"):
        print("INF")
    else:
        print(dist[i])

• 2 이상의 양수: 가장 큰 수부터 오름차순 정렬 순서대로 다음 숫자와 곱해서 더하기

• 1: 전부 더해주기
• 0 또는 음수: 가장 작은 수부터 오름차순 정렬 순서대로 다음 숫자와 곱해서 더하기

import sys

input = sys.stdin.readline

n = int(input())

plus_nums = []
other_nums = []
ones = 0

for i in range(n):
    line = int(input())
    if line == 1:
        ones += 1
    elif line > 1:
        plus_nums.append(line)
    else:
        other_nums.append(line)

# 순서대로 정렬하기
plus_nums.sort()
other_nums.sort()

# 최대 합
ans = 0

p_len = len(plus_nums)

# 양수는 맨 뒤에서부터 시작
i = p_len - 1

# 1) 양수 처리
while i >= 0:
    if i - 1 >= 0:
        ans += plus_nums[i] * plus_nums[i - 1]
        i -= 2
    else:
        ans += plus_nums[i]
        i -= 1

o_len = len(other_nums)

# 2) 1 처리 (전부 더해주기)
ans += ones


# 음수는 맨 앞에서부터 시작
i = 0

# 3) 0 또는 음수 처리
while i < o_len:
    # 뒤에 두 개 이상 남은 경우 곱해주기
    if i + 1 < o_len:
        ans += other_nums[i] * other_nums[i + 1]
        i += 2
    else:
        ans += other_nums[i]
        i += 1

print(ans)

선이 교차하지 않아야 함 -> 순서 유지 -> 최대한 많은 연결 -> 최장증가부분수열의 길이 구하는 문제!

from bisect import bisect_left


n = int(input())
ports = list(map(int, input().split()))

# print(ports)


lis = []

for i in range(n):
    pos = bisect_left(lis, ports[i])

    if pos == len(lis):
        lis.append(ports[i])
    else:
        lis[pos] = ports[i]


print(len(lis))

• 리스트에 튜플 형태로 저장 시 각 값의 저장 순서 주의하기

• 여러 경우의 수에 대해 시뮬레이션하는 경우 매 턴마다 입력받은 맵을 deepcopy해서 써야 함
• while문 종료 조건에 들어간 변수 매번 갱신 주의

from itertools import combinations
from collections import deque


# 1) m만큼의 자리에 궁수 3명을 성에 배치할 수 있는 경우의 수(0 ~ m-1 의 숫자중 3개 고르는 모든 조합 구하기)
# 2) 궁수와 D거리 이하인 적 중 가장 가까운, 가장 왼쪽에 있는 적 공격(여러 궁수가 하나의 적 공격 가능)
# 3) 공격된 적은 죽음
# 4) 남은 적 아래로 한칸씩 모두 이동
# 5) 성에 도착한 적은 제외
# 6) 위를 반복하다 모든 적이 제외되면 종료


line = list(map(int, input().split()))


n, m, d = line[0], line[1], line[2]

maps = []


for i in range(n):
    line = list(map(int, input().split()))
    maps.append(line)


killer_area = list(range(0, m))
area_combi = list(combinations(killer_area, 3))


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


def kill_enemies(killer_list, copy_maps):

    enemy_list = []
    kill_cnt = 0

    for k in killer_list:  # 킬러 위치: [n][k]

        q = deque()
        visited = [[False] * m for _ in range(n)]

        q.append((n, k))
        # visited[n-1][k] = True

        candidates = []

        while q:
            x, y = q.popleft()

            for i in range(3):
                nx, ny = x + dx[i], y + dy[i]

                dist = abs(nx - n) + abs(ny - k)

                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                    if copy_maps[nx][ny] == 1 and dist <= d:
                        candidates.append((dist, nx, ny))
                    elif copy_maps[nx][ny] == 0 and dist <= d:
                        q.append((nx, ny))
                    visited[nx][ny] = True

        if len(candidates) > 1:
            candidates.sort(key=lambda x: (x[0], x[2]))
            enemy_list.append(candidates[0])
        elif len(candidates) == 1:
            enemy_list.append(candidates[0])

    # 각 궁수가 죽일 적 리스트 처리
    for dist, x, y in enemy_list:  # 저장 순서 주의!!!
        if copy_maps[x][y] == 1:
            copy_maps[x][y] = 0
            kill_cnt += 1

    return kill_cnt


def move_enemies(copy_maps):

    # 적 아래로 한칸씩 이동
    for i in range(n - 1, -1, -1):
        for j in range(0, m):
            if copy_maps[i][j] == 1:  # 적이 있는 경우

                if i == n - 1:
                    copy_maps[i][j] = 0
                else:
                    copy_maps[i][j] = 0
                    copy_maps[i + 1][j] = 1

    return


max_kill_cnt = -1

for i in range(0, len(area_combi)):
    killer_list = area_combi[i]

    # 매 턴마다 입력받은 맵 복사해서 써야함 주의
    copy_maps = [row[:] for row in maps]

    turn_cnt = 0  # 이번 조합에 죽인 적 수

    enemy_sum = 0
    for j in range(0, n):
        enemy_sum += sum(copy_maps[j])

    # 맵에 적이 없을 때까지 반복
    while enemy_sum > 0:

        kill_cnt = kill_enemies(killer_list, copy_maps)
        turn_cnt += kill_cnt  # 누적
        move_enemies(copy_maps)

        # 매 공격 턴 끝난 후에 맵에 남은 적 다시 계산해주기!!
        enemy_sum = 0
        for j in range(0, n):
            enemy_sum += sum(copy_maps[j])

    # 게임 종료되면 최댓값 갱신
    max_kill_cnt = max(max_kill_cnt, turn_cnt)


print(max_kill_cnt)

1) dp[x]: 현재까지 고려한 동전으로 x원을 만드는 조합(순서무시)의 개수 2) 초기값: dp[0] = 1 (아무 동전도 안 쓰는 1가지 경우) 3) 루프 순서: 동전 바깥, 금액 오름차순 (조합 + 무한사용) 4) 점화식 : dp[value] += dp[value - c] 는 마지막에 동전 c를 하나 더 쓴 경우(동전 c를 쓰기 위해 value - c한 경우의 수)를 누적함

n, k = map(int, input().split())

coins = []
for i in range(n):
    line = int(input())
    coins.append(line)


# dp[x] : 현재까지 고려한 동전들로 x원을 만드는 조합의 개수
dp = [0] * (k + 1)
dp[0] = 1


# 순서가 상관없는 경우(조합)에는 동전 루프를 바깥 루프로 (순서 상관있는 경우에는 동전 루프를 안쪽 루프로)
for c in coins:
    # 값은 오름차순으로 해야 무한 사용 가능! (내림차순 = 중복 안될때)
    for value in range(c, k + 1):
        dp[value] += dp[value - c]

print(dp[k])

1) 트리에서 임의의 정점 s에서 가장 먼 정점 a를 찾기 2) 이 a는 지름 경로의 한 끝점! 3) 다시 a에서 BFS를 돌려 가장 먼 정점과 그 거리를 구하기 -> 이때의 가장 먼 거리가 트리의 지름 -> BFS 2번으로 O(N)에 해결 가능함!

from collections import defaultdict, deque
import sys

input = sys.stdin.readline

v = int(input())
graph = defaultdict(list)
leaf_nodes = []


for i in range(v):
    line = list(map(int, input().split()))
    idx = line[0]
    j = 1
    while line[j] != -1:
        graph[idx].append((line[j], line[j + 1]))
        j += 2
    if j == 3:
        leaf_nodes.append(idx)


def bfs(start):
    q = deque()
    visited = [False] * (v + 1)

    q.append((start, 0))
    visited[start] = True  # 시작점 방문처리 잊지 말기!

    max_dist = -1
    max_node = 0

    while q:
        node, dist = q.popleft()

        if dist > max_dist:
            max_dist = dist
            max_node = node

        child = graph[node]

        for c, e in child:
            if not visited[c]:
                visited[c] = True
                q.append((c, dist + e))

    return max_dist, max_node


dist, node = bfs(1)
dist, node = bfs(node)
print(dist)

import sys
from collections import deque


input = sys.stdin.readline

n = int(input())

maps = []
s_size = 2  # 초기 상어 크기(2)
s_pos_x = -1  # 상어 x좌표(행)
s_pos_y = -1  # 상어 y좌표(열)
sec = 0  # 누적 시간

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

for i in range(n):
    line = list(map(int, input().rstrip().split()))
    for j in range(len(line)):

        if line[j] == 9:  # 상어 초기 좌표 초기화하기
            s_pos_x, s_pos_y = i, j
            line[j] = 0  # 맵에는 빈공간으로 표시

    maps.append(line)


def check_possible_fish():

    visited = [[False] * n for _ in range(n)]

    queue = deque()
    queue.append((s_pos_x, s_pos_y, 0))

    visited[s_pos_x][s_pos_y] = True

    # 현재 상어의 위치 및 크기일 때 접근해서 먹을 수 있는 후보 물고기 리스트
    eat_candidates = []

    while queue:
        x, y, dist = queue.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if (
                0 <= nx < n
                and 0 <= ny < n
                and maps[nx][ny] <= s_size
                and not visited[nx][ny]
            ):
                fish_size = maps[nx][ny]

                # 현재 자리에 물고기가 있는데(0 < maps[nx][ny]) 그 크기가 상어보다 작다면
                if 0 < fish_size < s_size:
                    # 후보 물고기 리스트에 추가, 그 뒤는 더 볼 필요 없음 (거리 상 가까운 물고기 먼저 먹기 때문에)
                    eat_candidates.append((nx, ny, dist + 1))
                else:  # 빈 공간이거나 물고기 크기가 상어랑 동일하다면 지나갈 수 있음
                    # 큐에 추가
                    queue.append((nx, ny, dist + 1))
                # 방문 처리
                visited[nx][ny] = True

    if len(eat_candidates) > 1:
        # 거리, 행, 열 순으로 정렬
        eat_candidates.sort(key=lambda x: (x[2], x[0], x[1]))

    return eat_candidates


eat_cnt = 0

while True:

    eat_candidates = check_possible_fish()

    # 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청
    if len(eat_candidates) == 0:
        break
    else:
        # 먹은 물고기 수 업데이트
        eat_cnt += 1
        # 상어 해당 물고기 자리로 이동
        s_pos_x, s_pos_y = eat_candidates[0][0], eat_candidates[0][1]
        # 먹어서 빈 공간으로 바꾸기
        maps[eat_candidates[0][0]][eat_candidates[0][1]] = 0
        # 이동 거리만큼 시간 누적
        sec += eat_candidates[0][2]

    # 상어 사이즈 키우기 (자신의 크기만큼의 마릿수를 먹으면 +1 커짐)
    if eat_cnt == s_size:
        s_size += 1
        eat_cnt = 0


print(sec)