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 | 31 |
Tags
- 포도주시식
- content script
- X
- 백준
- 파이썬
- Message Passing
- supabase
- Chrome Extension
- react
- 크롬 익스텐션
- 캠스터디
- 2156
- C언어로 쉽게 풀어쓴 자료구조
- discord.js
- 백준 7579
- 디스코드 봇
- TypeScript
- 공부시간측정어플
- 갓생
- nodejs
- background script
- 백준 #7568번 #파이썬 #동적계획법
- webpack
- 프로그래머스 #정수삼각형 #동적계획법
- popup
- 동적계획법
- 크롬 확장자
- 자료구조
Archives
- Today
- Total
히치키치
[백준] 16234번 : 인구이동 - Python(파이썬) 본문
https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
풀이
- 탐색 : 인접한 칸, 이동
- 연합 국가 구하기 탐색 -> 인구 수 업데이트
- BFS : 연합 국가 탐색 : 이동 -> 제한 조건 만족 -> 방문 표시
- 인구 수 업데이트 : 더이상 이동 불가 -> 연합 국가 간의 인구 수 구하기 -> 업데이트
- 이동 횟수 증가 : 인구 수 업데이트 한 번 끝나면 증가
코드
#https://www.acmicpc.net/problem/16234
import sys
sys.setrecursionlimit(100000)
'''
#Maximum recursion depth exceed
이 코드에서 재귀의 깊이는 약 2500이 될 수 있습니다.
하지만 파이썬3에는 기본 재귀 제한이 있고 이게 약 1000회 정도입니다.
파이파이3는 이보다 재귀 제한이 더 높아서 통과되는 것으로 보입니다.
파이썬3로 통과하려면 아래와 같은 코드를 상단에 추가하면 됩니다.
'''
N, L, R = map(int, input().split())
lists = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
cnt = 0
def go(x, y):
for i in range(4):
_x = x + dx[i]
_y = y + dy[i]
if 0 <= _x < N and 0 <= _y < N and visited[_x][_y]:
tmp = abs(lists[x][y] - lists[_x][_y])
if L <= tmp <= R:
visited[_x][_y] = False
combine.append([_x, _y])
go(_x, _y)
while True:
visited = [[True] *N for _ in range(N)]
flag = True
for i in range(N):
for j in range(N):
combine = []
if visited[i][j]:
combine.append([i, j])
visited[i][j] = False
go(i, j)
if len(combine) > 1:
flag = False
avg = int(sum([lists[x][y] for x, y in combine]) // len(combine))
for x, y in combine:
lists[x][y] = avg
if flag:
break
cnt += 1
print(cnt)
'알고리즘 스터디' 카테고리의 다른 글
[백준] 2839번 : 설탕배달 - Python(파이썬) (0) | 2021.03.30 |
---|---|
[백준] 11399번 : ATM - Python(파이썬) (0) | 2021.03.30 |
[백준] 1939번 : 중량제한 - Python(파이썬) (0) | 2021.03.22 |
[백준] 1339번 : 단어수학 - Python(파이썬) (0) | 2021.03.22 |
[백준] 2630번 : 색종이 만들기 - Python(파이썬) (0) | 2021.03.22 |
Comments