[ BOJ / Python ] 1743번 음식물 피하기
이번 문제는 깊이우선탐색을 통해 쉽게 해결하였다. 통로에 1이 있을 경우 1을 0으로 바꿔주고 4가지 방향으로 탐색을 진행하며 각 탐색마다 카운팅 변수를 1 증가시키고 결과적으로 카운팅 변수를 반환하는 재귀함수를 작성하여 해결하였다.
- 재귀 제한을 늘려준다.
- dfs함수를 h, w, cnt를 인자로 갖도록 선언한다.
->path[h][w]
를 0으로 갱신한다.
-> 4가지 탐색 방향을 저장하는 리스트 dh, dw를 선언하고 4가지 탐색 방향을 짝지어 저장한다.
-> 4번 반복하는 i에 대한 for문을 돌린다.
--> nh를h+dh[i]
로 갱신한다.
--> nw를w+dw[i]
로 갱신한다.
--> 만약 nh, nw가 0보다 크고, nh가 n보다 작거나 같고, nw가 m보다 작거나 같고,path[nh][nw]
가 1일 경우, cnt를dfs(nh, nw, cnt+1)
로 갱신한다.
-> cnt를 반환한다. - n, m, k를 입력받는다.
- 통로에 해당하는 리스트 path를 선언하고 0을
(n+1)*(m+1)
로 채워준다. - 결과를 저장하는 변수 answer를 0으로 선언한다.
- k번 반복하는 for문을 돌린다.
-> r, c를 입력받는다.
->path[r][c]
를 1로 갱신한다. - 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
-> 1부터 m까지 반복하는 j에 대한 for문을 돌린다.
--> 만약path[i][j]
가 1일 경우 answer를 answer과dfs(i, j, 1)
중 더 큰 값으로 갱신한다. - answer를 출력한다.
Code
import sys
sys.setrecursionlimit(10**9)
def dfs(h, w, cnt):
path[h][w]=0
dh=[0, 0, -1, 1]
dw=[1, -1, 0, 0]
for i in range(4):
nh=h+dh[i]
nw=w+dw[i]
if nh>0 and nw>0 and nh<=n and nw<=m and path[nh][nw]==1:
cnt=dfs(nh, nw, cnt+1)
return cnt
n, m, k=map(int, input().split())
path=[[0]*(m+1) for _ in range(n+1)]
answer=0
for _ in range(k):
r,c=map(int, input().split())
path[r][c]=1
for i in range(1, n+1):
for j in range(1, m+1):
if path[i][j]==1:
answer=max(answer, dfs(i, j, 1))
print(answer)
import sys
sys.setrecursionlimit(10**9)
def dfs(h, w, cnt):
path[h][w]=0
dh=[0, 0, -1, 1]
dw=[1, -1, 0, 0]
for i in range(4):
nh=h+dh[i]
nw=w+dw[i]
if nh>0 and nw>0 and nh<=n and nw<=m and path[nh][nw]==1:
cnt=dfs(nh, nw, cnt+1)
return cnt
n, m, k=map(int, input().split())
path=[[0]*(m+1) for _ in range(n+1)]
answer=0
for _ in range(k):
r,c=map(int, input().split())
path[r][c]=1
for i in range(1, n+1):
for j in range(1, m+1):
if path[i][j]==1:
answer=max(answer, dfs(i, j, 1))
print(answer)
Author And Source
이 문제에 관하여([ BOJ / Python ] 1743번 음식물 피하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-1743번-음식물-피하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)