Coding 공부

import sys
import heapq
def check(node):

    path_set = set()
    stack = [(node,distance[node])]

    while stack:
        node,dis = stack.pop()
        for prev_node in graph[node]:
            if (prev_node,node) not in path_set:
                if distance[prev_node] + graph[prev_node][node] == dis:
                    path_set.add((prev_node,node))
                    stack.append((prev_node,distance[prev_node]))
    if (G,H) in path_set or (H,G) in path_set:
        return True
    return False



def dijkstra(node):
    distance[node] = 0
    node_list = []
    heapq.heappush(node_list,(0,node))
    while node_list:
        cur_dis, cur_node = heapq.heappop(node_list)
        if distance[cur_node] > cur_dis:
            continue
        for next_node in graph[cur_node]:
            if distance[next_node] > graph[cur_node][next_node] + cur_dis:
                distance[next_node] = graph[cur_node][next_node] + cur_dis
                heapq.heappush(node_list,(graph[cur_node][next_node] + cur_dis,next_node))

    


input = sys.stdin.readline

for _ in range(int(input())):
    N,M,T = map(int,input().split())
    graph = [{} for _ in range(N+1)]
    start,G,H = map(int,input().split())
    for _ in range(M):
        x,y,pay = map(int,input().split())
        graph[x][y] = pay
        graph[y][x] = pay
    
    candidate_list = [int(input().rstrip()) for _ in range(T)]
    INF = float('inf')
    distance = [INF]*(N+1)
    dijkstra(start)
    result = []
    for check_node in candidate_list:
        if check(check_node):
            result.append(check_node)

    result.sort()
    print(*result)

import sys

input = sys.stdin.readline

def combination(ind,len_string,combi):
    if ind == len_string:
        print(combi)
    else:
        for k in range(len_string):
            if visited[k]:
                temp = combi+string_list[k]
                if temp not in record:
                    visited[k] = False
                    record.add(temp)
                    combination(ind+1,len_string,temp)
                    visited[k] = True 



N = int(input())

for _ in range(N):
    string_list = list(input().strip())
    string_list.sort()
    len_string = len(string_list)
    visited = [True]*(len(string_list))
    record = set()
    combination(0,len_string,'')

from collections import deque
def find_passenger(start,K):
    stack = deque()
    stack.append((*start,K))
    visited = [[True]*N for _ in range(N)]
    visited[start[0]][start[1]] = False
    if passenger_arr[start[0]][start[1]] < 0:
        result = [start[0],start[1],K,passenger_arr[start[0]][start[1]]]
        passenger_arr[start[0]][start[1]] = 0
        return result

    candidate = []
    while stack:
        x,y,fuel = stack.popleft()
        if fuel < 0:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if passenger_arr[nx][ny] <=0 and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny,fuel-1))
                    if passenger_arr[nx][ny] < 0:
                        candidate.append([nx,ny,fuel-1,passenger_arr[nx][ny]])
    if candidate:
        candidate.sort(key=lambda x : (-x[2],x[0],x[1]))
        result = candidate[0]
        passenger_arr[result[0]][result[1]] = 0
        return result
    else:
        return False

def find_destination(passenger):
    stack = deque()
    stack.append((passenger[0],passenger[1],passenger[2]))
    destination = destination_dict[passenger[-1]]
    visited = [[True]*N for _ in range(N)]
    visited[passenger[0]][passenger[1]] = False
    init_fuel = passenger[2]
    while stack:
        x,y,fuel = stack.popleft()
        if fuel <= 0:
            return False
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <N and 0<=ny<N:
                if passenger_arr[nx][ny] <=0 and visited[nx][ny]:
                    visited[nx][ny] = False
                    stack.append((nx,ny,fuel-1))
                    if (nx,ny) == destination:
                        fuel = 2*init_fuel - fuel + 1
                        result = [nx,ny,fuel]
                        return result

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

passenger_arr = [list(map(int,input().split())) for _ in range(N)]
destination_dict = {}
taxi = list(map(lambda x : x-1 ,map(int,input().split())))
ind = 2



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

for _ in range(M):
    start_x,start_y,end_x,end_y = map(lambda x : x-1 ,map(int,input().split()))
    passenger_arr[start_x][start_y] = -ind
    destination_dict[-ind] = (end_x,end_y)
    ind += 1


answer = 0
cnt = 0
while cnt <M:
    passenger = find_passenger(taxi,K)
    if not passenger:
        answer = -1
        break
    destination = find_destination(passenger)
    if not destination:
        answer = -1
        break
    taxi = [destination[0],destination[1]]
    K = destination[-1]
    if K < 0:
        answer = -1
        break
    cnt += 1


if answer == -1:
    print(answer)
else:
    print(K)

경로 중간에 fuel이 0이 되어도 false 반환 안되게 함

N,M,K = map(int,input().split())
# N 은 격자
# M 은 상어의 수
# K 은 이동횟수

sharks = {}
arr = []
smell = {}
for x in range(N):
    input_list = list(map(int,input().split()))
    for y in range(N):
        if input_list[y]:
           sharks[input_list[y]] = (x,y)
           smell[(x,y)] = [K,input_list[y]]
    arr.append(input_list)
# 0 위 1 아래 2 왼쪽 3 오른쪽

shark_input_move = list(map(int,input().split()))
ind = 1
for shark_init_move in shark_input_move:
    sharks[ind] = (*sharks[ind],shark_init_move-1)
    ind += 1

shark_move = [[],]

for _ in range(M):
    temp = []
    for x in range(4):
        move_input = list(map(lambda x : x-1,map(int,input().split())))
        temp.append(move_input)
    shark_move.append(temp)



time = 0


dx = [-1,1,0,0]
dy = [0,0,-1,1]
while time <= 1000:
    move_shark = {}
    new_smell = {}
    for shark_num in sorted(sharks.keys()):
        x,y,dire = sharks[shark_num]
        shark_move_direction = []
        for i in shark_move[shark_num][dire]:
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <N and 0<=ny <N:
                if not smell.get((nx,ny)):
                    shark_move_direction = (nx,ny,i)
                    break
        else:
            new_dire_list = shark_move[shark_num][dire]
            for new_dire in new_dire_list:
                nx = x + dx[new_dire]
                ny = y + dy[new_dire]
                if 0<=nx<N and 0<=ny<N:
                    if smell[(nx,ny)][1] == shark_num:
                        shark_move_direction = (nx,ny,new_dire)
                        break
        if not new_smell.get((nx,ny)):
            new_smell[(nx,ny)] = [K,shark_num]
            move_shark[shark_num] = shark_move_direction
    for position in smell.keys():
        if not new_smell.get(position):
            if smell[position][0]-1>0:
                new_smell[position] = [smell[position][0]-1,smell[position][1]]
    time += 1
    print(move_shark)
    print(new_smell)
    if time == 14:
        break
    if len(move_shark.keys()) == 1:
        break
    sharks = {}
    for shark_num in move_shark.keys():
        sharks[shark_num] = move_shark[shark_num] 
    smell = {position : new_smell[position] for position in new_smell.keys()}


print(-1 if time == 1001 else time)

N,M,K = map(int,input().split())
# N 은 격자
# M 은 상어의 수
# K 은 이동횟수

sharks = {}
arr = []
smell = {}
for x in range(N):
    input_list = list(map(int,input().split()))
    for y in range(N):
        if input_list[y]:
           sharks[input_list[y]] = (x,y)
           smell[(x,y)] = [K,input_list[y]]
    arr.append(input_list)
# 0 위 1 아래 2 왼쪽 3 오른쪽

shark_input_move = list(map(int,input().split()))
ind = 1
for shark_init_move in shark_input_move:
    sharks[ind] = (*sharks[ind],shark_init_move-1)
    ind += 1

shark_move = [[],]

for _ in range(M):
    temp = []
    for x in range(4):
        move_input = list(map(lambda x : x-1,map(int,input().split())))
        temp.append(move_input)
    shark_move.append(temp)



time = 0


dx = [-1,1,0,0]
dy = [0,0,-1,1]
while time <= 1000:
    move_shark = {}
    new_smell = {}
    for shark_num in sorted(sharks.keys()):
        x,y,dire = sharks[shark_num]
        shark_move_direction = []
        my_shark_move_direction = []
        my_smell_move = True
        for i in shark_move[shark_num][dire]:
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <N and 0<=ny <N:
                if not smell.get((nx,ny)):
                    shark_move_direction = (nx,ny,i)
                    break
                elif my_smell_move and smell[(nx,ny)][1] == shark_num:
                    my_smell_move = False
                    my_shark_move_direction = (nx,ny,i) 
        else:
            shark_move_direction = my_shark_move_direction[:]
        
        if not new_smell.get((shark_move_direction[0],shark_move_direction[1])):
            new_smell[(shark_move_direction[0],shark_move_direction[1])] = [K,shark_num]
            move_shark[shark_num] = shark_move_direction
    for position in smell.keys():
        if not new_smell.get(position):
            if smell[position][0]-1>0:
                new_smell[position] = [smell[position][0]-1,smell[position][1]]
    time += 1
    if len(move_shark.keys()) == 1:
        break
    sharks = {}
    for shark_num in move_shark.keys():
        sharks[shark_num] = move_shark[shark_num] 
    smell = {position : new_smell[position] for position in new_smell.keys()}


print(-1 if time == 1001 else time)

import copy
def find_position(pools,num):
    for x in range(4):
        for y in range(4):
            if pools[x][y][0] == num:
                return (x,y)
    return False
def move_fish(pools,shark_x,shark_y):
    for fish_num in range(1,17):
        position = find_position(pools,fish_num)
        if position:
            x,y = position
            fish_dire = pools[x][y][1]

            for _ in range(8):
                nx = x + dx[fish_dire]
                ny = y + dy[fish_dire]
                if 0<=nx<4 and 0<=ny<4:
                    if not (nx == shark_x and ny == shark_y):
                        pools[x][y][0],pools[nx][ny][0] = pools[nx][ny][0],pools[x][y][0]
                        pools[x][y][1],pools[nx][ny][1] = pools[nx][ny][1],fish_dire
                        break
                fish_dire = (fish_dire+1)%8


def eating(x,y,pools):
    temp = []
    shark_dire = pools[x][y][1]
    for _ in range(3):
        nx = x + dx[shark_dire]
        ny = y + dy[shark_dire]
        if 0<=nx<4 and 0<=ny<4 and pools[nx][ny][0]>0:
            temp.append((nx,ny))
        x,y = nx,ny
    return temp


def solution(pools,shark_x,shark_y,cnt):
    global answer
    pools2 = [[col[:] for col in row]      for row in pools]
    eat_fish_size = pools2[shark_x][shark_y][0]
    pools2[shark_x][shark_y][0] = -1
    move_fish(pools2,shark_x,shark_y)
    find_fish = eating(shark_x,shark_y,pools2)
    answer = max(answer,eat_fish_size+cnt)

    for x,y in find_fish:
        solution(pools2,x,y,cnt+eat_fish_size)
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]

pools = []
for x in range(4):
    arr = list(map(int,input().split()))
    temp = []
    for y in range(4):
        fish_number,dire = arr[2*y],arr[2*y+1]
        temp.append([fish_number,dire-1])
    pools.append(temp)
answer = 0

solution(pools,0,0,0)
print(answer)

def find_K(k,n,reversal):
    if n == 0:
        return reversal%2
    else:
        if k >= 2**(n-1):
            return find_K(abs(2**(n-1)-k),n-1,reversal+1)
        else:
            return find_K(k,n-1,reversal)

k = int(input())
k = k-1
print(find_K(k,60,0))

import sys

input = sys.stdin.readline

def move(target):
    x,y,dire = chess[target]

    nx = x + dx[dire]
    ny = y + dy[dire]

    if not(0<=nx<N) or not(0<=ny<N) or arr[nx][ny] == 2:
        dire = reverse_dire[dire]
        chess[target] = [x,y,dire]
        nx = x + dx[dire]
        ny = y + dy[dire]
        if not(0<=nx<N) or not(0<=ny<N) or arr[nx][ny] == 2:
            return 0

    slice_idx = 0
    for ind,horse in enumerate(chess_map[x][y]):
        if horse == target:
            slice_idx = ind
            break

    move_items = chess_map[x][y][slice_idx:]
    chess_map[x][y] = chess_map[x][y][:slice_idx]

    if arr[nx][ny]:
        move_items.reverse()

    chess_map[nx][ny].extend(move_items)

    for ind in move_items:
        chess[ind] = [nx,ny,chess[ind][2]]
    
    return len(chess_map[nx][ny]) 



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

arr = [list(map(int,input().split())) for _ in range(N)]

chess = [[] for _ in range(M)]
chess_map = [[[] for _ in range(N)] for _ in range(N)]

chess_input = [list(map(lambda x : x-1,map(int,input().split()))) for _ in range(M)]


dx = [0,0,-1,1]
dy = [1,-1,0,0]
reverse_dire = [1,0,3,2]


for ind,info in enumerate(chess_input):
    x,y,dire = info
    chess[ind] = [x,y,dire]
    chess_map[x][y].append(ind)


cnt = 0
break_flag = False
while cnt <= 1000:
    cnt += 1

    for k in range(M):
        stack_size = move(k)
        if stack_size >= 4:
            break_flag = True
            break
    if break_flag:
        break

print(-1 if cnt > 1000 else cnt)

N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]

result = float('inf')
for x in range(N):
    for y in range(N):
        for d1 in range(1,y+1):
            for d2 in range(1,N-y+1):
                if 0<=x+d1+d2<N and 0<=y+d2-d1<N and 0<=y+d2<N and 0<=y-d1<N: 
                    max_person = 0
                    min_person = float('inf')
                    visited = [[True]*N for _ in range(N)]
                    temp = 0
                    d1_move = 0
                    d1_flag = True
                    d2_move = 0
                    d2_flag = True
                    for x_five in range(x,x+d2+d1+1):
                        for y_five in range(y-d1_move,y+d2_move+1):
                            visited[x_five][y_five] = False
                            temp += arr[x_five][y_five]
                        if d1_flag:
                            if d1_move == d1:
                                d1_flag = False
                                d1_move -=1
                            else:
                                d1_move += 1
                        else:
                            d1_move -= 1
                        
                        if d2_flag:
                            if d2_move == d2:
                                d2_flag = False
                                d2_move -= 1
                            else:
                                d2_move += 1
                        else:
                            d2_move -= 1
                    max_person = max(max_person,temp)
                    min_person = min(min_person,temp)

                    for x_area,y_area in [[(0,x+d1),(0,y+1)],[(0,x+d2+1),(y+1,N)],[(x+d1,N),(0,y-d1+d2)],[(x+d2+1,N),(y-d1+d2,N)]]:
                        temp = 0
                        for i in range(x_area[0],x_area[1]):
                            for j in range(y_area[0],y_area[1]):
                                if visited[i][j]:
                                    temp += arr[i][j]

                        max_person = max(max_person,temp)
                        min_person = min(min_person,temp)

                    result = min(result,max_person - min_person)

print(result)

def get_points(N):
    temp = []
    for x in range(1,N-1):
        for y in range(2,N):
            for d1 in range(1,y):
                for d2 in range(1,N-y+1):
                    if x + d1 + d2 >N:
                        break
                    temp.append([x,y,d1,d2])
    return temp

def divide_city(x,y,d1,d2):
    board = [[0]*N for _ in range(N)]
    for i in range(x+d1):
        for j in range(y):
            board[i][j] = 1
    
    for i in range(x+d2):
        for j in range(y,N):
            board[i][j] = 2

    for i in range(x+d1-1,N):
        for j in range(y-d1+d2-1):
            board[i][j] = 3

    for i in range(x+d2,N):
        for j in range(y-d1+d2-1,N):
            board[i][j] = 4

    for i in range(d1+d2+1):
        for j in range(-(d1-abs(i-d1)), d2+1-abs(i-d2)):
            board[x+i-1][y+j-1] = 5

    return board


N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]

divide_possible_list = get_points(N)

result = float('inf')
for x,y,d1,d2 in divide_possible_list:
    board = divide_city(x,y,d1,d2)
    persons = [0]*5
    for i in range(N):
        for j in range(N):
            persons[board[i][j]-1] += arr[i][j]

    diff = max(persons) - min(persons)
    if diff < result:
        result = diff
print(result)