Algorithm/λ°±μ€€

[λ°±μ€€] 7576 ν† λ§ˆν†  (파이썬/python)

chjcoder 2023. 8. 2. 22:38

🎈문제

https://www.acmicpc.net/problem/7569

 

πŸŽμ–΄λ–€ μ•Œκ³ λ¦¬μ¦˜?

1. μΈμ ‘ν•œ ν† λ§ˆν† κ°€ 읡게 λ§Œλ“œλ―€λ‘œ bfsλ₯Ό μ‚¬μš©ν•΄μ•Όκ² λ‹€κ³  νŒλ‹¨ν•¨

2. μ‹œμž‘μ μ΄ μ—¬λŸ¬κ°œμΈ bfs 문제의 경우, μ‹œμž‘μ μ„ λͺ¨λ‘ 큐에 λ„£κ³  bfsλ₯Ό λŒλ¦¬λŠ” 것이 핡심이닀.

 

 

 

πŸ’»μ½”λ“œ

# 7576 ν† λ§ˆν† 

from collections import deque

def bfs():
    # μƒν•˜μ’Œμš° μ’Œν‘œ μ„€μ •
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    while deq:
        x,y = deq.popleft() # νμ—μ„œ 읡은 ν† λ§ˆν†  μ’Œν‘œ κΊΌλ‚΄κΈ°
        for i in range(4):  # μƒν•˜μ’Œμš° 탐색 μ‹œμž‘
            nx = x + dx[i]
            ny = y + dy[i]
            # graph λ²—μ–΄λ‚œ μ’Œν‘œλŠ” λ¬΄μ‹œ
            if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                continue
            if graph[nx][ny] == 0:  # μ•ˆμ΅μ€ ν† λ§ˆν†  발견
                graph[nx][ny] = graph[x][y] + 1 # λ‚ μ§œ+1
                deq.append([nx,ny])

# n: μ„Έλ‘œ(x), m: κ°€λ‘œ(y)
m,n = map(int,input().split())

#graph
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))


deq = deque()   # 큐 μ„€μ •

# 탐색 μ‹œμž‘
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            deq.append([i,j])

# bfsλŒλ €μ„œ ν† λ§ˆν†  읡히기
bfs()

# 읡지 λͺ»ν•˜λŠ” ν† λ§ˆν†  확인 및 κ±Έλ¦¬λŠ” λ‚ μ§œ 확인
all_ripe = True # ν† λ§ˆν† κ°€ λͺ¨λ‘ μ΅μ—ˆλŠ”μ§€ 확인할 λ³€μˆ˜
day = 0 # ν† λ§ˆν† κ°€ λͺ¨λ‘ 읡을 λ•ŒκΉŒμ§€μ˜ μ΅œμ†Œ λ‚ μ§œ

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:    # 아직 μ•ˆμ΅μ€ ν† λ§ˆν† κ°€ μ‘΄μž¬ν•˜λ©΄
            all_ripe = False
            print(-1)
            break
        day = max(day,graph[i][j])
    if not all_ripe:
        break

if all_ripe:    # ν† λ§ˆν†  λͺ¨λ‘ μ΅μ—ˆμœΌλ©΄
    print(day-1)