Coding 공부

# 2493번 탑
from collections import deque
N = int(input())
arr =  list(map(int,input().split()))
result = [0]*N
stack = deque()
for ind in range(N):
    while stack and stack[len(stack)-1][1] < arr[ind]:
        stack.pop()
    if stack:
        result[ind] = stack[len(stack)-1][0]
    else:
        result[ind] = 0
    stack.append((ind+1,arr[ind])) 


    
print(*result)

   이 문제는 스택을 이용해 구현하는 문제인데, 스택과 큐와 같은 기본이 좀 부실하다보니 푸는데 어려움을 겪었던 문제였다.

첫 풀이는 앞에서부터 탐색하는 방식이다.

스택에는 앞에서부터 차근차근 인덱스와 탑의 높이를 넣어놓는다. 

그리고 스택에 놓여져있을때, 스택의 마지막 값이 탐색하는 탑의 높이보다 크거나 같을때 까지 계속 pop을 해준다. 

그리고 만약에 스택이 남아있으면 마지막 값을 결과값에 넣어주고, 아니면 0을 넣어준다.

예를 들어 설명하겠다.

7 3 5 9 2 8 이 있다고 하자

tower :  7 3 5 6 2 8

ind : 0

stack : []

result : [0,0,0,0,0,0]

처음에는 stack이 비어져있고, 가장 첫번째는 무조건 0이기 때문에 stack에 현재 타워의 index와 높이를 넣어준다.

tower : 7 3 5 9 2 8

ind : 1

stack : [(1,7)]

result : [0,1,0,0,0,0]

다음 타워는 높이가 3인데 스택의 끝에 있는 타워보다 높이가 낮기 때문에 그대로 수신이 가능하다. 그래서 결과에는 스택의 마지막에 있는 타워의 index를 넣어주고 stack에 넣어준다.

tower : 7 3 5 9 2 8

ind : 2

stack : [(1,7),(2,3)]

result : [0,1,1,0,0,0]

여기서 봐보면 현재 tower의 높이는 5이다. 하지만 stack에 끝에 있는 타워의 높이는 3이다. 그러면 이 tower에는 절대 다른 타워에서 수신을 할 수 없다. 왜냐하면 높이가 5인 타워가 높이가 3인 타워를 가리기 때문에, 신호를 수신할 수 없다. 그렇기 때문에 stack에서 없애주고, 그 다음 끝값과 비교한다. 여기서는 현재타워의 높이가 5이고, 스택의 마지막은 7이기 때문에 1번째 타워에서 신호가 수신이 가능하고, stack에 넣어준다.

tower : 7 3 5 9 2 8

ind : 3

stack : [(1,7),(3,5)]

result : [0,1,1,0,0,0]

위와 같은 방식으로 하면 스택내에는 현재 타워의 높이인 9보다 높은 타워가 없기 때문에 스택이 전부 비워지고, 결과값에는 0을 넣어줄 수 있다

tower : 7 3 5 9 2 8

ind : 4

stack : [(4,9)]

result : [0,1,1,0,4,0]

현재 타워의 높이가 2이므로 스택의 끝값보다 작기 때문에 수신이 가능하다. 그리고 스택에 넣어주면 된다.

tower 7 3 5 9 2 8

ind : 5

stack : [(4,9),(5,2)]

result : [0,1,1,0,4,4]

똑같이 진행해주면 된다.

위와 같이 스택의 특성을 알고, 하나하나 진행해주면 쉬운 문제인데, 알고리즘 기초인 스택과 큐에 대해서 약하다보니 오래걸렸던 문제이다.

N = int(input())
arr = list(map(int,input().split()))

result = [0]*N
stack = []

for ind in range(N-1,-1,-1):
    while stack and arr[stack[-1]] < arr[ind]:
        result[stack.pop()] = ind + 1
    stack.append(ind)

print(*result)

이 방법은 끝에서부터 진행하는 방법이다. stack에 인덱스를 넣어주고 거꾸로 오면서 stack에 끝에 있는 값이 현재의 타워보다 작을때, 그때 stack에서 꺼내서 결과값에 저장하는 방식이다.

# 실패한 방법

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

arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
max_size = min(N,M)

for x in range(N):
    for y in range(M):
        if result == max_size:
            break
        if arr[x][y] == 1:
            for sizes in range(result,max_size+1):
                temp = 0
                for dx in range(sizes):
                    for dy in range(sizes):
                        if 0<=x+dx<N and 0<=y+dy<M: 
                            temp += arr[x+dx][y+dy]
                if temp == sizes**2:
                    result = sizes
                else:
                    break
print(result**2)

처음에 단순하게 현재의 max_size만큼을 각 위치에서 탐색을 해서 갱신해주는 방식을 했다. 이렇게 하니 시간 초과가 나왔다.

N,M = map(int,input().split())
arr = [[0]*(M+1)]
for _ in range(N):
    arr.append([0]+list(map(int,list(input()))))
result = 0
max_size = min(N,M)

for x in range(1,N+1):
    for y in range(1,M+1):
        if arr[x][y]:
            arr[x][y] = min(arr[x-1][y],arr[x][y-1],arr[x-1][y-1])+1
            result = max(arr[x][y],result)
        if result == max_size:
            break

print(result**2)

위와 같은 정사각형이 있으면,  우하단을 기준으로 상하, 대각선이 전부 1이어야만 정사각형이 모양이된다. 만약 3개 중 하나라도 0이 있으면 크기가 2인 정사각형이 모양이 안된다. 그러므로 여기서 될수 있는 정사각형의 크기는 2이다.

이걸 좀 더 확장해서 3*3를 그려보도록 하자.

위와 같이 있다고 했을때 행과 열 중 0인 곳은 크기가 1를 초과하는 것을 못 만드므로 예외로 하겠다. 그러면 실질적으로 1,1 부터 탐색을 한다.

위와 같은 로직으로 하면 다음과 같이 우하단이 3이 되는 것을 알 수 있다 

이렇게 한군데가 비어있으면

이렇듯 우하단이 2가 되는 것을 알 수 있다.

그러므로 이 문제는 (x,y) 좌표 기준으로 (x-1,y),(x,y-1),(x-1,y-1)의 값의 최소값에 + 1을 해주면 된다.

그리고 저장된 값 중에서 가장 큰 값이 이 행렬에서 제일 큰 정사각형이므로, 제곱을 해서 출력을 하면 된다.

# 2225번 합분해


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

dp = [[1]*(N+1) if i==0 else [0]*(N+1) for i in range(K)]


for ind in range(1,K):
    for prev_num in range(N,-1,-1):
        for current_num in range(N,-1,-1):
            if prev_num + current_num <=N:
                dp[ind][prev_num+current_num] += dp[ind-1][prev_num]


print(dp[K-1][N]%1000000000)

K 번을 더햇 N이 나오는 경우이므로, DP를 (N+1)*K 형태로 만들어 놨다. 그래서 이전 행에서의 prev_num과 현재의 current_num을 더해서 N을 넘지 않는 경우 새로운 행에 그 횟수를 저장해주는 방식을 해주었다.

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

dp = [[1]*(N+1) if ind==0 else [0]*(N+1) for ind in range(K)]


for k in range(1,K):
    for num in range(N+1):
        dp[k][num] = (dp[k-1][num] + dp[k][num-1])%1000000000

print(dp[K-1][N])

위의 방식대로 풀어도 시간내에 통과하지만 점화식을 구하면 좀 더 쉽게 구할 수 있다.

DP[K][N] = DP[K-1][N] + DP[K-1][N-1] + .... + DP[K-1][0] 이다.

DP[K][N-1] = DP[K-1][N-1] + DP[K-1][N-2] + .... + DP[K-1][0] 인 것을 알 수 있따.

이것을 봐보면 DP[K][N] = DP[K-1][N] + DP[K][N-1]인 것을 알 수 있다.

이 점화식을 통해 구하면 좀 더 쉽게 구할 수 있다.

# # 3190 뱀
from collections import deque

N = int(input())
K = int(input())
apples = set(tuple(map(int,input().split())) for _ in range(K))
command_cnt = int(input())
# direction 0동 1남 2서 3북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
commands = []
snakes = deque()
snakes.append((1,1))
for _ in range(command_cnt):
    time,dire = input().split()
    if dire == 'D':
        dire = 1
    else:
        dire = -1
    commands.append((int(time),dire))

snake_times = 0
ind = 0
snake_direction = 0
flag = True
next_time = commands[0][0]
break_flag = False
while True:
    if flag:
        next_time = commands[ind][0]


    snake_times += 1

    snake_head = snakes[0]
    next_x = snake_head[0] + dx[snake_direction]
    next_y = snake_head[1] + dy[snake_direction]
    if 1<= next_x <=N and 1<= next_y<=N:
        if (next_x,next_y) not in snakes:
            if (next_x,next_y) in apples:
                snakes.appendleft((next_x,next_y))
                apples.remove((next_x,next_y))
            else:
                snakes.pop()
                snakes.appendleft((next_x,next_y))
        else:
            break_flag = True
    else:
        break_flag = True
    if break_flag:
        break



    if snake_times == next_time:
        snake_direction = (snake_direction + commands[ind][1])%4
        ind += 1
        if ind == command_cnt:
            flag = False
print(snake_times)

이 문제는 큐와 스택같은 자료구조에 대해서 알면 쉽게 풀 수 있는 문제이다.

물론 나는 오래걸렸다.

먼저 여기서는 방향 전환이 왼쪽, 오른쪽 밖에 없다. 만약에 동남서북(0,1,2,3) 형태로 방향을 저장해놓은 상태라면, 왼쪽일때는 -1을 해주고 오른쪽일때는 +1 을 해주고, 4로 나눈 나머지를 구해주면 된다.

기본적인 방법은 다음과 같다. snake는 기본적으로 deque 형태로 저장을 해준다.

먼저 snake_head를 기준으로 탐색해야한다. 나는 deque에서 왼쪽 즉 처음 들어온부분이 head로 가정했기 때문에, snake[0]을 가져온다. 그리고 snake의 방향에 맞게 진행을 해준다. 만약 범위를 벗어나거나 이미 snake에 있는 위치로 갈시, 예외처리를 해주고, 즉각적으로 멈출수 있게 break_flag를 해주었다.

그리고 둘 중 하나인데 만약에 뱀의 머리가 움직인 위치에 사과가 있을때에는, 뱀의 길이가 늘어난 것이기 때문에 새로운 head의 위치를 snake에 추가해주고, apple를 없애준다.

만약에 사과가 없을때에는 꼬리부분을 없애주고, 새로운 머리부분을 추가해준다.

매 타임마다 위와 같이 진행을 해주면 되는데, 여기서 명령어가 주어진다. 여기서 주의할 점은 시간이 끝난뒤 시행되는 것이기 때문에 time을 늘려주는 로직을 이 명령어를 조작하는 부분보다 상위에 두어야한다.

뱀이 움직이 시간이 끝난 시간과 명령어에 들어온 시간이 같으면 명령어 대로 방향을 바꿔준다.

그리고 이 명령어의 길이가 3일때, 만약에 3번째 명령까지 반영해서 방향을 바꿔주었으면 마지막 방향대로 계속 진행을 해야하기 때문에 flag를 통해 예외 처리를 해주었다.

# # 3190 뱀
from collections import deque

N = int(input())
K = int(input())
board = [[0]*(N+1) for _ in range(N+1)]
for _ in range(K):
    x,y = map(int,input().split())
    board[x][y] = 1

command_cnt = int(input())

# direction 0동 1남 2서 3북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
commands = []
snakes = deque()
snakes.append((1,1))
board[1][1] = 2
for _ in range(command_cnt):
    time,dire = input().split()
    if dire == 'D':
        dire = 1
    else:
        dire = -1
    commands.append((int(time),dire))

snake_times = 0
ind = 0
snake_direction = 0
next_time,next_direction = commands[0]
break_flag = True
while True:


    snake_times += 1

    snake_head = snakes[0]
    next_x = snake_head[0] + dx[snake_direction]
    next_y = snake_head[1] + dy[snake_direction]
    if 1<= next_x <=N and 1<= next_y<=N:
        if board[next_x][next_y] != 2:
            if board[next_x][next_y] == 1:
                snakes.appendleft((next_x,next_y))
                board[next_x][next_y] = 2
            else:
                board[next_x][next_y] = 2
                tail_x,tail_y = snakes.pop()
                board[tail_x][tail_y] = 0
                snakes.appendleft((next_x,next_y))
            break_flag = False
    if break_flag:
        break
    break_flag = True



    if snake_times == next_time:
        snake_direction = (snake_direction + next_direction)%4
        if ind < command_cnt-1:
            ind += 1
            next_time,next_direction = commands[ind]

print(snake_times)

위의 내가 했던 부분과 거의 동일하다. 대신 board라는 2차원 리스트에 뱀의 위치와 사과의 위치를 표시해주었다 이렇게 하면, 첫번째 코드에서 썼던 not in snakes와 같은 logN이 걸리는 시간이 좀 더 줄어드는 장점이 있다.

from collections import deque

def bfs(x,y,color):
    global N
    stack = deque()
    stack.append((x,y))
    if color == 'B':
        chk = 2
    else:
        chk = 3
    visited[x][y] = chk
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if not visited[nx][ny] and arr[nx][ny] == color:
                    visited[nx][ny] = chk
                    stack.append((nx,ny))
    
def new_bfs(x,y,chk):
    global N
    stack = deque()
    stack.append((x,y))
    visited[x][y] = 0
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <=nx<N and 0<=ny<N:
                if visited[nx][ny] == chk:
                    visited[nx][ny] = 0
                    stack.append((nx,ny))

N = int(input())


arr = [list(input()) for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [[0]*N for _ in range(N)]
cnt_a = 0
cnt_b = 0
for x in range(N):
    for y in range(N):
        if not visited[x][y]:
            bfs(x,y,arr[x][y])
            cnt_a += 1

for x in range(N):
    for y in range(N):
        if visited[x][y]:
            new_bfs(x,y,visited[x][y])
            cnt_b += 1

print(cnt_a,cnt_b)

2개의 BFS로 나누어, 3개의 색으로 구분할때와 2가지 색으로 구분할때 나눠서 탐색해주면 된다.

여기서 별다른 건 없고, visited 라는 리스트를 두번 만드는게 싫어서, 첫번째 bfs에서 visited에 체크하는 숫자를 청색 vs 녹색,빨간색을 서로 다르게 해주었고,

두번째 bfs에서는 원본 배열이 아닌 visited 함수를 통해 bfs를 돌려주었다.

# 14503 로봇 청소기

# r,c 는 r은 북쪽(X) c는 서쪽(Y)
# 동서남북
# sudo
# 1. 현재위치 청소
# 2. 현재 위치에서 왼쪽으로 회전 + 전진 -> 청소 반복
#  없으면 그 방향으로 계속 회전
# 4방향 전부 청소 완료하면 한칸 후진
# 후진이 안되면 멈춤
# d 0,1,2,3 북동남서
# 빈칸은 0, 벽은 1
N,M = map(int,input().split())
robotX,robotY,direction = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
rotate = [3,0,1,2]
visited = [[True] *M for _ in range(N)]
cnt = 1
stack = [(robotX,robotY,direction)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
visited[robotX][robotY] = False
while stack:
    x,y,cu_dire = stack.pop()
    if visited[x][y]:
        visited[x][y] = False
        cnt += 1
    for _ in range(4):
        nx = x + dx[rotate[cu_dire]]
        ny = y + dy[rotate[cu_dire]]
        if 0<= nx <N and 0<= ny<M:
            if visited[nx][ny] and not arr[nx][ny]:
                stack.append((nx,ny,rotate[cu_dire]))
                break
        cu_dire = rotate[cu_dire]
    else:
        reverse_dire = (cu_dire+2)%4
        nx = x + dx[reverse_dire]
        ny = y + dy[reverse_dire]
        if 0<= nx< N and 0<= ny <M and not arr[nx][ny]:
            stack.append((nx,ny,cu_dire))
        else:
            break

print(cnt)

    

이 문제는 문제에 주어진 조건대로 구현을 하는 문제였다. 

문제에 주어진 조건대로 구현을 하면 되는데, 여기서 몇가지 주의점이 있다. 보통 DFS나 BFS에서는 시간을 아껴주기 위해, stack에 append 할때 방문을 표시해준다. 하지만 여기서는 한번 청소했던 곳을 다시 방문할 수 있고, 청소는 단 한번만 해주기 때문에, stack에서 빼줄때, 그때 visitied를 방문표시를 해주고, 청소회수를 늘려주었다. 이러는게 문제에 주어진 구현 순서인 1번에 적합한 것 같다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

2.1 ~ 2.2 구간이 중간에 있는 반복문에 있는 부분이다. 여기서는 사전에 작업을 해주었다. 위에 주석에도 있지만, 0,1,2,3을 북동남서로 저장해주고, 그에 해당되는 dx,dy를 구현해주었다. 

그리고, rotate라는 변수에, 인덱스값은 현재의 방향 그리고 값은 왼쪽으로 회전시 나오는 방향을 넣어주었다.

평소에는 북남동서등 같은 방향끼리, 하는 경우가 많은데 여기서는 북동남서로 2칸씩 떨어트린 이유는 후진을 구현할때, 이렇게 2칸씩 떨어트려주면 (direction+2)%4 로 하면 쉽게 방향을 구할 수 있기 때문이다. 정 아니면 rotate와 동일하게 후진시 변경되는 리스트를 미리 만들어둬도 된다.

이렇게 반복문을 다 돌렸는데도 한번도 만족하지 않으면, else로 들어가 2.3~2.4 로직을 진행한다.

후진이 가능하면, stack에 집어넣고, 그렇지 않으면 종료를 해주면 된다.

구현관련된 문제는 하나씩 단계별로 구현하는 연습을 더 자주해야할것 같다.

# 16946 벽 부수고 이동하기 4

# dfs를 해준다. 여기서 일반적인 dfs와 다른점은 방문표시 대신 해당 위치의 값을 들어온 index값으로 변형시켜준다.
def dfs(x,y,index):
    global index_dict,N,M

    stack = [(x,y)]
    cnt = 1
    arr[x][y] = index
    while stack:
        cx,cy = stack.pop()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if not arr[nx][ny]:
                    stack.append((nx,ny))
                    arr[nx][ny] = index
                    cnt += 1
    # dfs를 전부 한뒤에 그 개수를 딕셔너리에 저장해준다.
    index_dict[index] = cnt




# dfs를 이용해서 쉽게 풀수 있었던 문제


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

dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,list(input()))) for _ in range(N)]
# 원본이 저장된 arr
result = [['0']*M for _ in range(N)]
# 결과값들을 저장해놓는 result 배열을 만들어둔다.

# 빈칸인 개수를 세주기 위해서 초기값을 -1로 해줬다. 왜냐하면 arr에는 1,0이 있으므로 겹쳐지지 않게 -1부터 시작해서 1씩 작아지게 해줬다.
# 그리고 해당 인덱스에 연결된 개수를 저장하기 위한 index_dict라는 딕셔너리를 미리 만들어줬다.
index = -1
index_dict = {}

# 빈칸의 개수를 세어주기 위한 dfs 공정
for x in range(N):
    for y in range(M):
        if not arr[x][y]:
            dfs(x,y,index)
            index -= 1

for x in range(N):
    for y in range(M):
        if arr[x][y] == 1:
            # 원본 배열에서 벽이 있을때, 그 벽 주변의 상황을 파악하고, 그 중에 1이 아닌 우리가 설정한 index값을 집합에 저장해준다.
            temp = set()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] != 1:
                        temp.add(arr[nx][ny])
            # 기본값은 1이고, temp에 저장된 index들을 반복문을 돌려 움직일수 있는 칸의 개수를 세준다.
            move_wall = 1
            for index in temp:
                move_wall += index_dict[index]
            # 그리고 result에 10으로 나눈 나머지를 string형태로 저장해준다.
            result[x][y] = str(move_wall%10)
# join을 이용해 출력해준다.
for row in result:
    print(''.join(row))

 이 문제는 union find 문제와 비슷하게 빈 위치의 그룹을 지어주면 된다.

최종 결과가 나올 result라는 2차원 배열을 '0'으로 초기화 해줬다. 왜냐하면, 나중에 출력을 할때, join을 쓰기 위해, 문자열 형태로 초기화 해줬다.

먼저 주어진 행렬의 빈칸들의 그룹의 정보를 저장해줄 index_dict을 만들어줬다. 여기서 key는 index 을 기준으로 해줬고, value는 그 그룹의 개수이다.

여기서 index 초기값을 -1을 해준 이유는 문제에서 0,1을 이미 쓰고 있어서, 겹치지 않기 위해 음수로 해줬다.

그러면 주어진 행렬에서 dfs 아니면 bfs를 해주면서, 빈칸들의 그룹들을 나눠 주는 작업을 해주고, 그 그룹의 크기와 index를 index_dict에 저장을 해주면서, 원본행렬에도 index를 대신 넣어준다.

벽 부수고 이동하기를 해주는 방법은 원본 행렬에서 1인 곳을 찾아서, 상하좌우에 있는 1이 아닌 값들을 집합에 저장을 해준다. 그리고 집합에 저장된 index들을 꺼내 전체 index_dict에 저장된 값들을 더해주면 된다. 그리고 원래 있던 벽이 무너지는 거니 1이 기본값이다.

그리고 결과값을 10으로 나눈 나머지를 문자열 형태로 저장해줬다.

# 1937 욕심쟁이 판다 실패(Fail)
def dfs(x,y):
    global N
    stack = [(x,y,0)]
    last_direction = []
    while stack:
        cx,cy,distance = stack.pop()
        flag = True
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx<N and 0<=ny<N:
                if bamboo[cx][cy] < bamboo[nx][ny]:
                    if dp[nx][ny] == -1:
                        stack.append((nx,ny,distance+1))
                    else:
                        if distance + dp[nx][ny] + 1 > dp[x][y]:
                            dp[x][y] = dp[nx][ny] + distance + 1
                           
                    flag = False
        if flag:
            if dp[x][y] < distance + 1:
                dp[x][y] = distance + 1



N = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
bamboo = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]

result = - 1
for x in range(N):
    for y in range(N):
        if dp[x][y] == -1:
            dfs(x,y)
print(max(map(max,dp)))

이 문제를 단순하게 DFS로 풀면 시간 초과가 날수 밖에 없다. 왜냐하면 입력이 최대가 500*500 이므로, dp를 통해 이미 탐색한 값들을 저장해놓는 과정이 필요하다. 위의 코드는 시간초과가 난 코드이다. 

dp를 사용하긴 했지만, 각 (x,y) 축에서 dfs를 하지만, 이 이동경로에 있는 좌표들에 대해서 이미 한번 측정한 값인데, 다시 한번 dp를 측정해야하는 것이다.

import sys


def dfs(x,y):
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if bamboo[nx][ny]>bamboo[x][y]:
                    distance = dfs(nx,ny) + 1
                    dp[x][y] = max(distance,dp[x][y])
        return dp[x][y]







N = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
bamboo = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]
result = - 1
for x in range(N):
    for y in range(N):
        if dp[x][y] == -1:
            dfs(x,y)

print(max(map(max,dp)))

재귀를 이용한, 이동 경로에 대해서 전부 한번에 업데이트를 해주는 것이다.

최초 이동경로에서 (x0,y0) = > (x1,y1) => (x2,y2) => ...=>(xn,yn) 각 경로마다 최대로 갈수 있는 이동경로들을 저장해준다. 그리고 return된 값에 + 1을 해줘 해당 칸에 갔을때의 이동거리를 측정해주고, 최대값을 갱신해주면 된다.

이렇게 하면 장점은 어느 곳에서 한번 방문했던 곳은 더 이상 dfs를 하지않고 해당 위치에서의 최대값을 반환해주는 것이다.

이 문제는 각 위치마다의 최대경로를 구하는 로직과, 그걸 이용해서 시간복잡도를 줄이는게 중요한 문제였다.