-
[Python] λ°±μ€ - 2468 μμ μμ__Python/__Algorithm 2022. 2. 22. 14:00
λ¬Έμ
https://www.acmicpc.net/problem/2468
πΉ λ¬Έμ
μ¬λλ°©μ¬μ²μμλ λ§μ λΉκ° λ΄λ¦¬λ μ₯λ§μ² μ λλΉν΄μ λ€μκ³Ό κ°μ μΌμ κ³ννκ³ μλ€. λ¨Όμ μ΄λ€ μ§μμ λμ΄ μ 보λ₯Ό νμ νλ€. κ·Έ λ€μμ κ·Έ μ§μμ λ§μ λΉκ° λ΄λ Έμ λ λ¬Όμ μ κΈ°μ§ μλ μμ ν μμμ΄ μ΅λλ‘ λͺ κ°κ° λ§λ€μ΄ μ§λ μ§λ₯Ό μ‘°μ¬νλ €κ³ νλ€. μ΄λ, λ¬Έμ λ₯Ό κ°λ¨νκ² νκΈ° μνμ¬, μ₯λ§μ² μ λ΄λ¦¬λ λΉμ μμ λ°λΌ μΌμ ν λμ΄ μ΄νμ λͺ¨λ μ§μ μ λ¬Όμ μ κΈ΄λ€κ³ κ°μ νλ€.
μ΄λ€ μ§μμ λμ΄ μ 보λ νκ³Ό μ΄μ ν¬κΈ°κ° κ°κ° NμΈ 2μ°¨μ λ°°μ΄ ννλ‘ μ£Όμ΄μ§λ©° λ°°μ΄μ κ° μμλ ν΄λΉ μ§μ μ λμ΄λ₯Ό νμνλ μμ°μμ΄λ€. μλ₯Ό λ€μ΄, λ€μμ N=5μΈ μ§μμ λμ΄ μ 보μ΄λ€.
λ¬Όμ μ κΈ°μ§ μλ μμ ν μμμ΄λΌ ν¨μ λ¬Όμ μ κΈ°μ§ μλ μ§μ λ€μ΄ μ, μλ, μ€λ₯Έμͺ½ νΉμ μΌμͺ½μΌλ‘ μΈμ ν΄ μμΌλ©° κ·Έ ν¬κΈ°κ° μ΅λμΈ μμμ λ§νλ€. μμ κ²½μ°μμ λ¬Όμ μ κΈ°μ§ μλ μμ ν μμμ 5κ°κ° λλ€(κΌμ§μ μΌλ‘λ§ λΆμ΄ μλ λ μ§μ μ μΈμ νμ§ μλλ€κ³ μ·¨κΈνλ€).
λν μμ κ°μ μ§μμμ λμ΄κ° 6μ΄νμΈ μ§μ μ λͺ¨λ μ κΈ°κ² λ§λλ λ§μ λΉκ° λ΄λ¦¬λ©΄ λ¬Όμ μ κΈ°μ§ μλ μμ ν μμμ μλ κ·Έλ¦Όμμμ κ°μ΄ λ€ κ°κ° λ¨μ νμΈν μ μλ€.
μ΄μ κ°μ΄ μ₯λ§μ² μ λ΄λ¦¬λ λΉμ μμ λ°λΌμ λ¬Όμ μ κΈ°μ§ μλ μμ ν μμμ κ°μλ λ€λ₯΄κ² λλ€. μμ μμ κ°μ μ§μμμ λ΄λ¦¬λ λΉμ μμ λ°λ₯Έ λͺ¨λ κ²½μ°λ₯Ό λ€ μ‘°μ¬ν΄ 보면 λ¬Όμ μ κΈ°μ§ μλ μμ ν μμμ κ°μ μ€μμ μ΅λμΈ κ²½μ°λ 5μμ μ μ μλ€.
μ΄λ€ μ§μμ λμ΄ μ λ³΄κ° μ£Όμ΄μ‘μ λ, μ₯λ§μ² μ λ¬Όμ μ κΈ°μ§ μλ μμ ν μμμ μ΅λ κ°μλ₯Ό κ³μ°νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
πΉ μ λ ₯
첫째 μ€μλ μ΄λ€ μ§μμ λνλ΄λ 2μ°¨μ λ°°μ΄μ νκ³Ό μ΄μ κ°μλ₯Ό λνλ΄λ μ Nμ΄ μ λ ₯λλ€. Nμ 2 μ΄μ 100 μ΄νμ μ μμ΄λ€. λμ§Έ μ€λΆν° Nκ°μ κ° μ€μλ 2μ°¨μ λ°°μ΄μ 첫 λ²μ§Έ νλΆν° Nλ²μ§Έ νκΉμ§ μμλλ‘ ν νμ© λμ΄ μ λ³΄κ° μ λ ₯λλ€. κ° μ€μλ κ° νμ 첫 λ²μ§Έ μ΄λΆν° Nλ²μ§Έ μ΄κΉμ§ Nκ°μ λμ΄ μ 보λ₯Ό λνλ΄λ μμ°μκ° λΉ μΉΈμ μ¬μ΄μ λκ³ μ λ ₯λλ€. λμ΄λ 1μ΄μ 100 μ΄νμ μ μμ΄λ€.
πΉ μΆλ ₯
첫째 μ€μ μ₯λ§μ² μ λ¬Όμ μ κΈ°μ§ μλ μμ ν μμμ μ΅λ κ°μλ₯Ό μΆλ ₯νλ€.
νμ΄ λ°©λ²
πΉ κ·Έλν νμ
πΉ BFS(λλΉμ°μ νμ)
πΉ νλ Έμ΅λλ€ ν΄κ²° > μ μΆλ ₯ μμ νλ¨μ μΆκ° μ λ³΄κ° μμλ€. "μ무 μ§μλ λ¬Όμ μ κΈ°μ§ μμ μλ μλ€."
μ¦, λͺ¨λ μμμ μ΅μ λμ΄ μ΄νλ‘ λ¬Όμ μ κ²Όμ μλ μλ€. (κ° μμ λμ΄ 3~9, 2 μ΄νλ‘ λ¬Όμ μ κ²Όμ λ)
λν, λΉκ° μ ν λ΄λ¦¬μ§ μμμ μλ μλ€. (λ¬Όμ μ κΈ΄ κΉμ΄ 0)
πΉ DFS νμ΄ μ, λ°νμ μλ¬(RecursionError)λ₯Ό ν΄κ²°νμ§ λͺ»νλ€.
πΉ μ΄μ μ νμλ λ¨μ§λ²νΈλΆμ΄κΈ° λ¬Έμ μ μ μ¬νλ€.
ꡬν μ½λ
import sys from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(q,h): while q: x,y = q.popleft() for k in range(4): nx = x + dx[k] ny = y + dy[k] if 0<=nx<n and 0<=ny<n and area[nx][ny]>h and visited[nx][ny]==0: visited[nx][ny] = 1 q.append([nx,ny]) n = int(sys.stdin.readline()) area = [list(map(int,sys.stdin.readline().split())) for _ in range(n)] M = max(max(area)) ans = 0 for h in range(0,M): cnt = 0 visited = [[0]*n for _ in range(n)] for i in range(n): for j in range(n): if area[i][j]>h and visited[i][j]==0: bfs(deque([[i,j]]),h) visited[i][j] = 1 cnt += 1 if cnt > ans: ans = cnt print(ans)
μ€ν κ²°κ³Ό
π‘
728x90'__Python > __Algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Python] λ°±μ€ - 1952 λ¬ν½μ΄ 2 (0) 2022.03.24 [Python] λ°±μ€ - 1913 λ¬ν½μ΄(κΈ°μ΄ λ°°μ΄λ€λ£¨κΈ°) (0) 2022.03.24 [Python] λ°±μ€ - 7569 ν λ§ν (0) 2022.02.12 [Python] λ°±μ€ - 1439 λ€μ§κΈ° (0) 2022.01.27 [Python] λ°±μ€ - 1629 κ³±μ (0) 2022.01.13