-
백준 1926 python백준/깊이 우선 탐색 2023. 3. 27. 16:45
문제
https://www.acmicpc.net/problem/1926
풀이
- DFS를 이용한다.
- 재귀로 풀 경우 메모리 초과가 발생하므로 stack을 이용한다.
n,m=map(int, input().split()) I,O=[[*map(int, input().split())] for _ in range(n)],[0,0] def dfs(sx,sy): stack,S=[],0 I[sx][sy]=0 stack.append([sx,sy]) while(len(stack)>0): x,y=stack.pop() S+=1 N=[[x-1,y],[x,y-1],[x,y+1],[x+1,y]] for nx,ny in N: if nx>=0 and nx<n and ny>=0 and ny<m and I[nx][ny]==1: I[nx][ny]=0 stack.append([nx,ny]) return S for i in range(n): for j in range(m): if I[i][j]==1: O[0]+=1 O[1]=max(O[1],dfs(i,j)) print(f'{O[0]}\n{O[1]}')
'백준 > 깊이 우선 탐색' 카테고리의 다른 글
백준 1043 nodejs (0) 2023.01.26 백준 2661 nodejs (0) 2023.01.18 백준 1520 nodejs (0) 2023.01.12 백준 1707 nodejs (0) 2023.01.02