DevYoon
[๋ฐฑ์ค] 1937. ์์ฌ์์ด ํ๋ค (Python) ๋ณธ๋ฌธ
link ๐ https://www.acmicpc.net/problem/1937
1๏ธโฃ ๋จน์ ๋๋๋ฌด ์๋ณด๋ค ๋ง์ ์ชฝ์ผ๋ก๋ง ์ด๋ํ๋ ํ๋ค
2๏ธโฃ ์ํ์ผ๋ก ํ์๋ค๊ฐ ์๊ฐ ์ด๊ณผ
3๏ธโฃ DFS + DP๋ก ํด๊ฒฐ
import sys
sys.setrecursionlimit(100000)
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
count = [[0]*n for _ in range(n)]
Max = 0
def DFS(y, x):
if count[y][x]: # ๋ค๋ฆฐ ์ ์์ผ๋ฉด
return count[y][x] # ๋ณธ์ธ ๋ฆฌํด
count[y][x] = 1 # ์ด๊ธฐ๊ฐ ๋ฃ์ด์ฃผ๊ธฐ
for i, j in dir:
dy, dx = y+i, x+j
if 0 <= dy < n and 0 <= dx < n:
if board[dy][dx] > board[y][x]: # ๋๋๋ฌด๊ฐ ๋ ๋ง์ด ์๋ ๊ณณ์ผ๋ก๋ง ์ด๋
count[y][x] = max(count[y][x], DFS(dy, dx)+1)
return count[y][x] # ์ํ์ข์ฐ ์ค ๋จน์ ์ ์๋ ๋๋๋ฌด๊ฐ ์์ผ๋ฉด ๋ณธ์ธ ๋ฆฌํด
for y in range(n):
for x in range(n):
if count[y][x] == 0:
Max = max(Max, DFS(y, x))
print(Max)
๐ข ๋ฒ์๊ฐ ๋๋ฌด ์ปค์ (๋๋๋ฌด์ ์์ด 1000000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค) RecursionError๋ฅผ ํผํ ์ ์์๋คใ ใ
๐ข ๊ตฌ๊ธ์ ๋์์ ๋ฐ์ ๊ฒฐ๊ณผ sys.setrecursionlimit(100000)๋ก ํ์ด์ฌ์ ์ฌ๊ท ๊น์ด ์ ํ์ ์์ ํด์ฃผ์๋ค.
๐ข ํ์ด์ฌ์ ์ต๋ ์ฌ๊ท ๊น์ด๊ฐ 1000์ผ๋ก ์์ ํธ์ด๋ผ, ์ฝํ ์์ ์ฌ๊ท ์ธ ๊ฒฝ์ฐ์๋ ์ ์ฝ๋๋ฅผ ์จ๋์์ผ ํ๋ ๋ชจ์์ด๋ค. ๋ ํ๋ ๋ฐฐ์ ๋ค...โ๏ธ