Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
Tags
- 스프링배치 csv
- spring batch 5
- 스프링 배치 5
- 선언적 트랜잭션 관리
- 아이템 리더 커스텀
- JSONObject 분할
- JSON 분할
- 스프링배치 메타테이블
- flatfileitemwriter
- spring batch 변수 공유
- api 아이템 리더
- mybatis
- abstractpagingitemreader
- executioncontext 변수 공유
- 마이바티스 트랜잭션
- 스프링배치 엑셀
- JSON 분리
- step 사이 변수 공유
- Spring Batch
- aop proxy
- 아이템 리더 페이징 처리
- job parameter
- 스프링 트랜잭션 관리
- 트랜잭션 분리
- step 값 공유
- step 여러개
- stepexecutionlistener
- executioncontext
- JSONArray 분할
- 읽기 작업과 쓰기 작업 분리
Archives
- Today
- Total
ebson
boj.kr/2573 빙산 (gold4) 파이썬 풀이 본문
1. 한 해가 지난 후 빙산 그래프 결과를 저장하고 0이 아닌 좌표를 ice_set에 저장
2. ice_set 을 순회하면서 방문체크하지 않은 좌표만을 대상으로 dfs를 수행, dfs 횟수를 저장
3. dfs 횟수가 2회 이상이면 year_cnt를 출력, 빙산 그래프에 얼음이 없으면 0을 출력
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)
def year_after(graph):
temp = [g[:] for g in graph]
for gy in range(1, N-1):
for gx in range(1, M-1):
if graph[gy][gx] > 0:
for i in range(4):
ny = gy + dy[i]
nx = gx + dx[i]
if 0<=ny<N and 0<=nx<M and graph[ny][nx] == 0:
temp[gy][gx] = temp[gy][gx]-1 if temp[gy][gx]-1>0 else 0
if temp[gy][gx] > 0:
ice_set.add((gy, gx))
return temp
import sys
sys.setrecursionlimit(10**6)
def dfs(y, x):
for j in range(4):
ny = y + dy[j]
nx = x + dx[j]
if 0<=ny<N and 0<=nx<M and not visited[ny][nx] and graph[ny][nx] > 0:
visited[ny][nx] = True
dfs(ny, nx)
year_cnt = 0
while True:
cnt = 0
visited = [[False] * M for _ in range(N)]
ice_set = set()
graph = [g[:] for g in year_after(graph)]
year_cnt += 1
for (cy, cx) in ice_set:
if not visited[cy][cx] and graph[cy][cx] > 0:
dfs(cy, cx)
cnt += 1
if cnt >= 2:
break
if len(ice_set) == 0:
year_cnt = 0
break
print(year_cnt)
그래프에 얼음이 없을 때까지 두개로 나누어지지 않는 경우 0을 출력하는 요구사항을 구현하지 않으면 답을 출력하지 못해 시간초과가 발생하므로 주의한다.
'ALGORITHM STUDY WITH PYTHON > BFS | DFS' 카테고리의 다른 글
boj.kr/1167 트리의 지름 (gold2) 파이썬 풀이 (0) | 2023.05.02 |
---|---|
boj.kr/1967 트리의 지름 (gold4) 파이썬 풀이 (0) | 2023.05.02 |
boj.kr/1707 이분 그래프 (gold4) 파이썬 풀이 (0) | 2023.05.01 |
boj.kr/1987 알파벳 (gold4) 파이썬 풀이 (0) | 2023.05.01 |
boj.kr/16234 인구 이동 (gold5) 파이썬 풀이 (0) | 2023.04.29 |