coding-test-book n회차 + 백준 + 프로그래머스

coding_test.py

############################
# 백준: 안전영역; grid 재사용할 수 있을듯
# https://www.acmicpc.net/problem/2468
############################
from collections import deque

N = int(input())
grid = [list(map(int, input().split())) for _ in range(N)]
cand = set()
for i in range(N):
    for j in range(N):
        _v = grid[i][j]
        cand.add(_v)
        
def drown(grid, level):
    grid_copy = [[1 if i >= level else 0 for i in l] for l in grid]
    return grid_copy

def bfs(grid_copy):
    cnt = 0
    for i in range(N):
        for j in range(N):
            if grid_copy[i][j] == 1:
                cnt += 1
                q = deque([])
                grid_copy[i][j] = 0
                q.append((i, j))
                while q:
                    x, y = q.popleft()
                    for dx, dy in zip([0,0,1,-1], [1,-1,0,0]):
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < N and 0 <= ny < N:
                            if grid_copy[nx][ny] == 1:
                                grid_copy[nx][ny] = 0
                                q.append((nx, ny))
    return cnt

MAX = -1
for level in cand:
    grid_copy = drown(grid, level)
    res = bfs(grid_copy)
    MAX = max(MAX, res)
print(MAX)

############################
# 백준: 토마토2; q사용X
# https://www.acmicpc.net/problem/7569
############################
M, N, H = map(int, input().split())
box = []
for _ in range(H):
    ls = [list(map(int, input().split())) for _ in range(N)]
    box.append(ls)
    
nxt_cand = []; target = 0
for b in range(H):
    for x in range(N):
        for y in range(M):
            if box[b][x][y] == 1:
                nxt_cand.append((b, x, y))
            if box[b][x][y] == 0:
                target += 1
                
time = 0; done = 0
while True:
    nxt_cand_temp = []
    for b, x, y in nxt_cand:
        for dbox, dx, dy in zip([0,0,0,0,1,-1], [0,0,-1,1,0,0], [1,-1,0,0,0,0]):
            nb, nx, ny = b+dbox, x+dx, y+dy
            if 0 <= nb < H and 0 <= nx < N and 0 <= ny < M:
                if box[nb][nx][ny] == 0:
                    box[nb][nx][ny] = 1
                    nxt_cand_temp.append((nb, nx, ny))
                    done += 1
    if len(nxt_cand_temp) < 1:
        break
    else:
        nxt_cand = nxt_cand_temp
        time += 1
        
if done == target:
    print(time)
else:
    print(-1)
    
###########################
# 백준: 미로탐색
# https://www.acmicpc.net/problem/2178
############################
from collections import deque
import math
N, M = map(int, input().split())
grid = [list(map(int, list(input()))) for _ in range(N)]

def bfs():
    q = deque([])
    q.append((0,0,1))
    while q:
        x, y, cost = q.popleft()
        for dx, dy in zip([0,0,1,-1], [1,-1,0,0]):
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M:
                if grid[nx][ny] == 1:
                    if nx == N-1 and ny == M-1:
                        print(cost+1)
                        return
                    grid[nx][ny] = 0
                    q.append((nx, ny, cost+1)) 
bfs()
############################
# 백준: 토마토
# https://www.acmicpc.net/problem/7576
############################
M, N = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(N)]

ok_list = []
nxt_list = []
target = M*N
for i in range(N):
    for j in range(M):
        if grid[i][j] == 1:
            nxt_list.append((i, j))
            ok_list.append((i, j))
        if grid[i][j] == -1:
            target -= 1

step = 0
while True:
    temp_nxt_list = []
    for x, y in nxt_list:
        for dx, dy in zip([0,0,1,-1], [1,-1,0,0]):
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M:
                if grid[nx][ny] == 0:
                    grid[nx][ny] = 1
                    ok_list.append((nx, ny))
                    temp_nxt_list.append((nx, ny))
    if len(temp_nxt_list) == 0:
        break
    else:
        nxt_list = temp_nxt_list
        step += 1

if len(ok_list) == target:
    print(step)
else:
    print(-1)

############################
# 백준: 1012 유기농배추
# https://www.acmicpc.net/problem/1012
############################

from collections import deque
def solution(N, M, loc):
    grid = [[0]*N for _ in range(M)]
    for x, y in loc:
        grid[x][y] = 1
        
    cnt = 0
    for i in range(M):
        for j in range(N):
            if grid[i][j] == 1:
                cnt += 1
                grid[i][j] = 2
                q = deque([])
                q.append((i, j))
                while q:
                    x, y = q.popleft()
                    for dx, dy in zip([0,0,1,-1], [1,-1,0,0]):
                        nx, ny = x+dx, y+dy
                        if 0 <= nx < M and 0 <= ny < N:
                            if grid[nx][ny] == 1:
                                q.append((nx, ny))
                                grid[nx][ny] = 2
    print(cnt)
    
T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    loc = [list(map(int, input().split())) for _ in range(K)]
    solution(N, M, loc)
    
############################
# 백준: 영역 구하기
# https://www.acmicpc.net/problem/2583
############################
from collections import deque

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

grid = [[0]*(M) for _ in range(N)]
for x, y, x2, y2 in cor:
    for i in range(x, x2):
        for j in range(y, y2):
            grid[i][j] = 1
            
ans = []
cnt = 0
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] == 1:
            continue
        q = deque([(i, j)])
        tracked = [(i, j)]
        grid[i][j] = 1
        cnt += 1
        while q:
            x, y = q.popleft()
            for dx, dy in zip([0,0,1,-1],[1,-1,0,0]):
                nx, ny = x + dx, y + dy
                if 0 <= nx < N and 0 <= ny < M:
                    if grid[nx][ny] == 0:
                        grid[nx][ny] = 1
                        tracked.append((nx, ny))
                        q.append((nx, ny))
        ans.append(len(set(tracked)))
print(cnt)
for i in sorted(ans):
    print(i, end=' ')

############################
# 백준: 인구이동(이코테21); 답지풀이
# https://www.acmicpc.net/16234
############################
from collections import deque

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

def iter_step(x, y, team_n):
    tracked = []
    tracked.append((x, y))
    q = deque()
    q.append((x, y))
    union[(x, y)] = team_n
    summation = A[x][y]
    n_union = 1
    while q:
        x, y = q.popleft()
        for dx, dy in zip([0,0,1,-1],[1,-1,0,0]):
            nx, ny = x+dx, y+dy
            if 0 <= nx < N and 0 <= ny < N and union[(nx, ny)] == -1:
                if L <= abs(A[x][y] - A[nx][ny]) <= R:
                    q.append((nx, ny))
                    summation += A[nx][ny]
                    union[(nx, ny)] = team_n
                    tracked.append((nx, ny))
                    n_union += 1

    for (i, j) in tracked:
        A[i][j] = summation // n_union
    return n_union

ans = 0
while True:
    union = {}
    for i in range(N):
        for j in range(N):
            union[(i, j)] = -1
    
    team_n = 0
    for x in range(N):
        for y in range(N):
            if union[(x, y)] == -1:
                n_union = iter_step(x, y, team_n)
                team_n += 1
    if team_n == N*N:
        break
    ans += 1
print(ans)

############################
# 백준: 인구이동(이코테21); 내풀이; 좌표 하나씩  iter -> while q
# https://www.acmicpc.net/16234
############################
import math
from collections import deque

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

def iter_population(A):
    global N, L, R
    team_dict = dict(); visited = set(); # {1:[(), (), (), ...], 2: ...}
    for i in range(N):
        for j in range(N):
            team_dict[(i, j)] = -1
            
    q = deque([])
    flag = False
    team_n = 0
    for i in range(N):
        for j in range(N):
            if team_dict[(i, j)] == -1:
                team_dict[(i, j)] = team_n
            else:
                continue
            summation = A[i][j]
            tracked = [(i, j)]
            q.append((i, j))
            while q:
                x, y = q.popleft()
                for dx, dy in zip([0,0,1,-1], [1,-1,0,0]):
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < N and 0 <= ny < N and team_dict[(nx, ny)] == -1:
                        if L <= abs(A[nx][ny]-A[x][y]) <= R:
                            summation += A[nx][ny]
                            tracked.append((nx, ny))
                            team_dict[(nx, ny)] = team_n
                            q.append((nx, ny))
                            flag = True
            # update
            for (_x, _y) in tracked:
                A[_x][_y] = summation // len(tracked)
            team_n += 1
    if not flag:
        return None
    else:
        return A

fin = False
ans = 0
while not fin:
    A_prime = iter_population(A)
    if A_prime is not None:
        A = A_prime
        ans += 1
    else:
        fin = True
print(ans)

############################
# 백준: 특정 거리의 도시 찾기
# https://www.acmicpc.net/submit/18352/42413803
############################

import math
from collections import deque

N, M, K, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    
start = [0, X]
min_dist = [math.inf]*(N+1)

q = deque([start])
min_dist[X] = 0
while q: # [(start to cur dist, cur_node)]
    dist, cur = q.popleft()
    for nxt in graph[cur]:
        updated_dist = dist + 1
        if min_dist[nxt] < updated_dist:
            continue
        else:
            min_dist[nxt] = updated_dist
            q.append([updated_dist, nxt])

ans = []
for node, val in enumerate(min_dist):
    if val == K:
        ans.append(node)
        
if len(ans) == 0:
    print(-1)
else:
    for i in ans:
        print(i)
        
############################
# 카카오 블록이동
# https://programmers.co.kr/learn/courses/30/lessons/60063
############################
from collections import defaultdict, deque
import math

DXDY = [(0, -1, 0, -1), (0, 1, 0, 1), (1, 0, 1, 0), (-1, 0, -1, 0)]  
def return_cand_cor(cur, board, N):
    a, b, c, d = cur
    for da, db, dc, dd in DXDY:
        yield (a+da, b+db, c+dc, d+dd)
        
    if a == c: # 가로
        if 0 <= a+1 < N:
            if board[a+1][b] != 1:
                yield (a+1,d,c,d)
        if 0 <= a-1 < N:
            if board[a-1][b] != 1:
                yield (a-1,d,c,d)
        if 0 <= c+1 < N:
            if board[c+1][d] != 1:
                yield (a,b,c+1,b)
        if 0 <= c-1 < N:
            if board[c-1][d] != 1:
                yield (a,b,c-1,b)
                
    elif b == d: # 세로
        if 0 <= a+1 < N and 0 <= b-1 < N:
            if board[a+1][b-1] != 1:
                yield (a,b,a,b-1)
        if 0 <= d+1 < N:
            if board[c][d+1] != 1:
                yield (a,b,a,b+1)
        if 0 <= b-1 < N:
            if board[a][b-1] != 1:
                yield (c,d-1,c,d)
        if 0 <= b+1 < N:
            if board[a][b+1] != 1:
                yield (c,d,c,d+1) 
                
def solution(board):
    N = len(board)
    min_dist = defaultdict(int)
    START = (0,0,0,1)
    min_dist[START] = math.inf
    q = deque([])
    q.append([0, START])
    MIN = math.inf
    while q:
        dist, cur = q.popleft() # cor: [(dist,(a,b,c,d))]
        for nxt in return_cand_cor(cur, board, N):
            na, nb, nc, nd = nxt
            (na, nb), (nc, nd) = sorted([(na, nb), (nc, nd)])
            nxt = (na, nb, nc, nd)
            if 0 <= na < N and 0 <= nb < N and 0 <= nc < N and 0 <= nd < N:
                if board[na][nb] == 0 and board[nc][nd] == 0:
                    updated_dist = dist + 1
                    if nc == N-1 and nd == N-1:
                        MIN = min(MIN, updated_dist)

                    if nxt not in min_dist:
                        min_dist[nxt] = updated_dist
                        q.append((updated_dist, nxt))
                    elif min_dist[nxt] <= updated_dist:
                        continue
                    else:
                        min_dist[nxt] = updated_dist
                        q.append([updated_dist, nxt])
    return MIN




############################
# 카카오 자물쇠
# 좌표 M+N 확인필요
############################
import copy
def solution(key, lock):
    M = len(key)
    N = len(lock)
    grid = [[0]*3*N for _ in range(3*N)]
    ANS = False
    # make grid
    intercept = N
    for i in range(N):
        for j in range(N):
            grid[intercept+i][intercept+j] = lock[i][j]

    def _check_answer(grid_copy):
        for i in range(N):
            for j in range(N):
                if grid_copy[N+i][N+j] != 1:
                    return False
        return True

    def move_key(grid, key):
        for inter_x in range(N-M+1, 2*N): 
            for inter_y in range(N-M+1, 2*N):
                grid_copy = copy.deepcopy(grid)
                for i in range(M):
                    for j in range(M):
                        grid_copy[i+inter_x][j+inter_y] += key[i][j]
                for l in grid_copy:
                    if _check_answer(grid_copy):
                        return True
        return False

    def rotate(key):
        res =[]
        tmp = []
        for l in zip(*key):
            l = list(reversed(l))
            tmp.append(l)
        for l in tmp:
            res.append(l)
        return res

    for _ in range(4):
        if move_key(grid, key):
            ANS = True
            break
        else:
            key = rotate(key)
    return ANS

############################
# 카카오 양궁대회
############################
from collections import deque

def calc_diff(P, cur):
    a = 0; b = 0
    for i in P:
        if i in cur: continue
        a += i
    b = sum(cur)
    return b - a

def return_ans(ans, INFO, P):
    _, remains, res = ans
    a = [0]*len(INFO)
    for i in res:
        if i in P: a[i] = INFO[i]+1
        else: a[i] = 1
    for _ in range(remains):
        a[0] += 1
    return a[::-1]

def solution(N, INFO):
    INFO = INFO[::-1]
    P = [i for i, j in enumerate(INFO) if j>0]
    ans = []; visited = []; start = [N, set()]; q = deque([start])
    while q:
        remains, cur = q.popleft()
        diff = calc_diff(P, cur)
        if diff > 0: ans.append([diff, remains, sorted(cur)])
        if remains <= 0: continue
        for i in range(1, 11):
            if i in cur: continue
            must = INFO[i] + 1
            nxt = cur|{i}
            if remains >= must and nxt not in visited:
                visited.append(nxt)
                tmp = [remains-must, visited[-1]]
                q.append(tmp)
    if len(ans) < 1: return [-1]
    ans = sorted(ans, key=lambda x: (x[0], x[1], -min(x[2])), reverse=True)[0]
    return return_ans(ans, INFO, P)

############################
# 이코테 Q 31 금광
# 아래코드는 첫 행 아무거나 선택할 경우를 고려
############################
from collections import defaultdict
import math

def solution(target):
    MAX = -math.inf
    N, M = len(target), len(target[0])
    dp = defaultdict(list)
    for i in range(N):
        for j in range(M):
            dp[(i, j)].extend([target[i][j]]*M)
    
    # M번 이동
    for cnt in range(M-1):
        for x in range(N):
            for y in range(M):
                for dx, dy in zip([-1,0,1], [1,1,1]):
                    nx, ny = x+dx, y+dy
                    if 0<=nx<N and 0<=ny<M:
                        dp[(nx, ny)][cnt+1] = max(dp[(x, y)][cnt] + dp[(nx, ny)][0], dp[(nx, ny)][cnt+1])
                        if cnt+1 == M-1:
                            MAX = max(MAX, dp[(nx, ny)][cnt+1])
                            
    return dp, MAX

################## input
T = int(input())
mat_ls = []

for _ in range(T):
    N, M = map(int, input().split())
    ls = list(map(int, input().split()))
    
    cnt = 0
    mat = []
    for i in range(N):
        tmp = []
        for j in range(M):
            tmp.append(ls[cnt])
            cnt += 1
        mat.append(tmp)
    mat_ls.append(mat)

################## main
for target in mat_ls:
    _dp, _val = solution(target)
    print(_val)
    for k, v in _dp.items():
        print(k,v)
        
############################
# 소인수분해
# https://www.acmicpc.net/problem/11653
############################

def do_sth(N):
    flag = False
    for i in range(2, int(N**(1/2))+1):
        a, b = divmod(N, i)
        if b == 0:
            flag = True
            break
    if flag:
        print(i)
        return do_sth(a)
    else:
        print(N)

N = int(input())
if N == 1:
    pass
else:
    do_sth(N)
    
############################
# 소수찾기
# https://www.acmicpc.net/problem/1978
############################
def is_prime(val):
    if val == 1:
        return False
    
    ans = True
    for i in range(2, int(val**(1/2))+1):
        if val % i == 0:
            ans = False
            break
            
    return ans

ls = list(map(int, input().split()))
cnt = 0
for i in ls:
    if is_prime(i):
        cnt += 1
print(cnt)

############################
# 이코테 Q 35 못생긴 수 
############################
root_ls = [0]*100001
root_ls[1] = 1
root_ls[2] = 1
root_ls[3] = 1
root_ls[5] = 1

def root(val):
    if root_ls[val] == 1:
        return 1
    elif root_ls[val] == 2:
        return 2
    else: # root_ls[val] == 0:
        if val%2 == 0:
            return root(val//2)
        elif val%3 == 0:
            return root(val//3)
        elif val%5 == 0:
            return root(val//5)
        else:
            return 2

ans = []
for i in range(1, 1000):
    aa = root(i)
    root_ls[i] = aa
    if aa == 1:
        ans.append(i)
        
############################
# DP 백준 퇴사
# https://www.acmicpc.net/problem/status/14501/1003/1
############################

import math
import copy

N = int(input())
ls = []
for _ in range(N):
    l = list(map(int, input().split()))
    ls.append(l)
    
dp = copy.deepcopy(ls)
MAX = -math.inf
for row in range(N):
    for col in range(row+1):
        val = dp[row][col]
        for dx, dy in zip([-1, -1], [0, -1]):
            nx, ny = row + dx, col + dy
            if 0 <= nx < N and 0 <= ny < row:
                dp[row][col] = max(dp[row][col], val + dp[nx][ny])
        MAX = max(MAX, dp[row][col])
print(MAX)

############################
# DP 백준 퇴사
# https://www.acmicpc.net/problem/status/14501/1003/1
############################
N = int(input())

ls = []
for _ in range(N):
    a, b = map(int, input().split())
    ls.append([a, b])
    
dp = [0]*N
for i in range(N):
    tmp = []
    for j in range(i+1):
        duration, money = ls[j]
        if j+duration-1 == i:
            if j > 0:
                tmp.append(dp[j-1]+money)
            else:
                tmp.append(money)
    if len(tmp) > 0:
        dp[i] = max(dp[i-1], max(tmp))
    else:
        if i == 0:
            dp[i] = 0
        else:
            dp[i] = dp[i-1]
print(max(dp))

############################
# p.351 Q20
# https://www.acmicpc.net/submit/18428/41528330
# while -> range바꿔보기
############################

from itertools import combinations
N = int(input())
mapping = {'X':0, 'S':1, 'T':2}
BLK = 4
grid = []
for _ in range(N):
    l = list(map(lambda x: mapping[x], input().split()))
    grid.append(l)
    
    
def candidate():
    ts_cor = []
    rows = set(); cols  = set()
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 2:
                rows.add(i)
                cols.add(j)
                ts_cor.append((i, j))
    
    cand = set()
    for i in rows:
        for j in range(N):
            if grid[i][j] == 0:
                cand.add((i, j))
                    
    for i in range(N):
        for j in cols:
            if grid[i][j] == 0:
                cand.add((i, j))
                          
    return list(cand), ts_cor

def gottcha(ts_cor):
    flag = False # True if get student
    for i, j in ts_cor:
        r = i; c = j
        while True:
            # row 고정
            c -= 1
            if c < 0:
                break
            if grid[i][c] == 1:
                flag = True
                return flag
            elif grid[i][c] == BLK:
                break
                
        r = i; c = j
        while True:
            # row 고정
            c += 1
            if N <= c:
                break
            if grid[i][c] == 1:
                flag = True
                return flag
            elif grid[i][c] == BLK:
                break
                
        r = i; c = j
        while True:
            # col 고정
            r -= 1
            if r < 0:
                break
            if grid[r][j] == 1:
                flag = True
                return flag
            elif grid[r][j] == BLK:
                break
                
        r = i; c = j
        while True:
            # col 고정
            r += 1
            if N <= r:
                break
            if grid[r][j] == 1:
                flag = True
                return flag
            elif grid[r][j] == BLK:
                break
                            
    return flag
                
def check(c, ts_cor):
    """return False if student got caught"""
    # place block
    for i, j in c:
        grid[i][j] = BLK
    
    # get caught
    if gottcha(ts_cor):
        # recover
        for i, j in c:
            grid[i][j] = 0
        return False
    else:
        for i, j in c:
            grid[i][j] = 0
        return True    


cand, ts_cor = candidate()
possible = False
for c in combinations(cand, 3):
    if check(c, ts_cor):
        print('YES') # possible; not caught
        possible = True
        break

if not possible:
    print('NO')
    
############################
# p.353 Q21
# https://www.acmicpc.net/submit/16234/41518885
############################
from collections import defaultdict, deque
import copy
import math
N, L, R = map(int, input().split())

A = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j, v in enumerate(map(int, input().split())):
        A[i][j+1] = v

def bfs(x, y, root, idx):
    global A, N, L, R
    is_updated = False
    root[x][y] = idx; val_sum = A[x][y]; tmp = [(x, y)]
    q = deque([(x, y)])
    while q:
        x, y = q.popleft()
        for dx, dy in zip([0,0,1,-1], [1,-1,0,0]):
            nx, ny = x + dx, y + dy
            if (1<=nx<=N and 1<=ny<=N) and root[nx][ny] < 0:
                if L<=abs(A[x][y]-A[nx][ny])<=R:
                    root[nx][ny] = idx
                    val_sum += A[nx][ny]
                    q.append((nx, ny))
                    tmp.append((nx, ny))
                    is_updated = True
    if is_updated:
        updated_val = math.trunc(val_sum/len(tmp))
        for x, y in tmp:
            A[x][y] = updated_val
    return is_updated

ans = 0
while True:
    root = [[-1]*(N+1) for _ in range(N+1)]
    idx = 0; flag = True
    for i in range(1, N+1):
        for j in range(1, N+1):
            idx += 1
            if root[i][j]  == -1:
                if bfs(i, j, root, idx):
                    flag = False
    if flag:
        break
    else:
        ans += 1

print(ans)

############################
# p.353 Q21
# https://www.acmicpc.net/submit/16234/41518885
# find union: 너무 오래걸림
############################
from collections import defaultdict, deque
import copy
import math

def find_root(root, a):
    if root[a] != a:
        root[a] = find_root(root, root[a])
    return root[a]

def union(a, b):
    a = find_root(root, a)
    b = find_root(root, b)
    if (a[0] > b[0]) and (a[1] > b[1]):
        root[b] = a
    else:
        root[a] = b
        
def bfs(q):
    global root, A, N, L, R
    is_updated = False
    while q:
        x, y = q.popleft()
        for dx, dy in zip([0,1], [1,0]):
            nx, ny = x + dx, y + dy
            if (1<=nx<=N and 1<=ny<=N):
                if L<=abs(A[x][y]-A[nx][ny])<=R:
                    if not find_root(root, (x, y)) == find_root(root, (nx, ny)):
                        union((x,y), (nx,ny))
                        is_updated = True
    return is_updated

def _update_root(root):
    for i in range(1, N+1):
        for j in range(1, N+1):
            find_root(root, (i, j))

def update_adj():
    global root, A
    _update_root(root)
    root_val = defaultdict(list)
    # 동일 root의 값 취합
    for k in root:
        r = root[k]
        root_val[r].append(A[k[0]][k[1]]) # {root: [vla, val,,,]}
    
    # root마다 평균값
    ks = root_val.keys()
    for k in ks:
        tmp = root_val[k]
        root_val[k] = math.trunc(sum(tmp)/len(tmp))
    
    # 모든 cor마다 값 업데이트
    for k in root:
        r = root[k]
        val = root_val[r]
        A[k[0]][k[1]] = val
    
    # reset root
    for i in range(1, N+1):
        for j in range(1, N+1):
            root[(i, j)] = (i, j)

##########################################main
N, L, R = map(int, input().split())
A = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j, v in enumerate(map(int, input().split())):
        A[i][j+1] = v
        
root = {}
for i in range(1, N+1):
    for j in range(1, N+1):
        root[(i, j)] = (i, j)
        
q = []
for i in range(1, N+1):
    for j in range(1, N+1):
        q.append((i, j))

ans = 0
while True:
    q_copy = copy.deepcopy(q)
    q_copy = deque(q_copy)
    is_updated = bfs(q_copy)
    if is_updated:
        update_adj()
        ans += 1
    else:
        break
print(ans)

############################
# p.339 Q15
############################

from collections import deque
import math

N, M, K, X = map(int, input().split())
distance = [math.inf]*(N+1)
adj = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    
def bfs(start_node):
    ans = []
    distance[start_node] = 0
    q = deque([[0, start_node]])
    while q:
        dist, cur = q.popleft()
        if dist > distance[cur]:
            continue        
        for nxt in adj[cur]:
            if distance[nxt] > dist + 1:
                distance[nxt] = dist + 1
                q.append([dist+1, nxt])

bfs(X)
flag = True
for i, val in enumerate(distance):
    if val == K:
        flag = False
        print(i)
if flag:
    print(-1)
    
############################
# 카카오 무지 먹방 라이브
############################

# 반례 Test case
# k = 12
# f_times = [3,6,5]
# return 3

# 추가 Test case
# k = 12
# f_times = [3,1,1,1,2,4,3]
# return 6

def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
    a, b = divmod(k, len(food_times))
    q = []
    for idx, val in enumerate(food_times):
        q.append((val, idx+1))
    q.sort()
    while True:
        tmp = []
        for (_elem, _idx) in q:
            _elem = _elem - a
            if _elem < 0:
                b += abs(_elem)           # 여기가 어려웠음
            if _elem > 0:
                tmp.append((_elem, _idx))
        tmp.sort()
        q = tmp

        a, b = divmod(b, len(q))
        if a == 0:
            break
    q = sorted(q, key=lambda x: x[1])
    return q[b-1+1][1]

############################
# p. 315; q. 5
# 다음 코인 type이 cum보다 작으면 (type <= cum)
# cum이하는 다 만들 수 있음
# type, cum
############################

# 집합 개념으로 생각해보면
# A 집합으로 1부터 n까지 생성가능;
# k라는 coin type이 추가되면;
# 1, ..., N은 원래되는 것이고
# 여기에 1+k, 2+k, ...., N+k까지 연속된 범위를 모두 충족시킬 수 있음
    # 예시
    # target_n == 현재 집합 원소로 만들 수 있는 연속된 수 중에서 가장 큰 수
      # coin_type == 11,  문제 발생!!!!!!!! 10을 만들 수 없음
      # coin_type == 10, target_n == 9라면, 19까지 가능
      # coin_type == 9, target_n == 9라면, 18까지 가능
      # coin_type == 8, target_n == 9라면, 17까지 가능
      # ...
      # target_n == 1 일 때, 새로 coin_type == 1 들어오면 -> 가능한 합산: 1, 2 
      # target_n == 1 일 때, 새로 coin_type == 2 들어오면 -> 1, .., 1+2 
      # target_n == 1 일 때, 새로 coin_type == 3 들어오면 -> 1, 삑!!!!!!!!!!! 
      # target_n == 9 일 때, 새로 coin_type == 1 들어오면 -> 1, ..., 9+1 
      # target_n == 9 일 때, 새로 coin_type == 8 들어오면 -> 1, ..., 9+8 
      # target_n == 9 일 때, 새로 coin_type == 9 들어오면 -> 1, ..., 9+9 
      # target_n == 9 일 때, 새로 coin_type == 10 들어오면 -> 1, ..., 10, ..., 9+10 
      # target_n == 9 일 때, 새로 coin_type == 11 들어오면 -> 1, ..., 9(원래 가능한 합산), 10 불가 삑!!!!!!!!!!!!!! 
      # 따라서 assert target_n <= (coin_type - 1)

ls = [3, 2, 1, 1, 9]
ls.sort()

assert ls[0] == 1
target_n = ls[0] # 1부터 시작
set_a = [ls[0]] # 공집합

for coin_type in ls[1:]:
    if coin_type-1 <= target_n:
        set_a.append(coin_type)
        target_n += coin_type
    else:
        break

print('maximum possible val', target_n, '; set for maxumum val', set_a) 

############################
# p. 315; q. 5
# 다음 코인 type이 cum보다 작으면 (type <= cum)
# cum이하는 다 만들 수 있음
# type, cum
############################

# 무게 달라야함
# 순열(조합X)
N = 5 # 볼링공갯수
M = 3 # 무기
ls = [1,3,2,3,2]

N = 8 # 볼링공갯수
M = 5 # 무기
ls = [1,5,4,3,2,4,5,2]

cnt  = 0
for i in range(0, len(ls)):
    for j in range(i+1, len(ls)):
        a = ls[i]
        b = ls[j]
        if a == b:
            continue
        cnt += 1
print(cnt)

############################
# p. 314; q. 4
# 다음 코인 type이 cum보다 작으면 (type <= cum)
# cum이하는 다 만들 수 있음
# type, cum
############################

coin_type = [3, 2, 1, 1, 9]
coin_type.sort()
cum = 1
for c in coin_type:
    if c > cum:
        print(cum)
        break
    else:
        cum += c

        
        
       


############################
# p. 259
############################

N, M = 5, 7
graph = [[], [2, 3, 4], [1, 4], [1, 4, 5], [1, 2, 3, 5], [3, 4]]
X, K = 4, 5

############################
# floyd warshall
############################
def floyd(distance):
    for k in range(1, N+1):
        for a in range(1, N+1):
            for b in range(1, N+1):
                distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])
    return distance

distance = [[INF]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in graph[i]:
        distance[i][j] = 1

distance = floyd(distance)
ans = distance[K] + distance[X]

############################
# dijk
############################

INF = math.inf
to_k_cost = [INF]*(N+1)
k_to_x_cost = [INF]*(N+1)

def dijik(start, distance):
    q = []
    heapq.heappush(q, (0, start))
    while q:
        s_to_a, a = heapq.heappop(q)
        if distance[a] < s_to_a:
            continue
        for b in graph[a]:
            new_s_to_b = s_to_a + 1
            if distance[b] > new_s_to_b:
                distance[b] = new_s_to_b
                heapq.heappush(q, (new_s_to_b, b))

dijik(1, to_k_cost)
ans = to_k_cost[K] + k_to_x_cost[X]