J1Yun
ZU-TECHLOG
J1Yun
전체 방문자
였늘
μ–΄μ œ
  • πŸ“‘ Category (135)
    • Algorithm (61)
      • πŸ“š Concept (6)
      • πŸ“˜ Baekjoon Judge (53)
      • πŸ“— Programmers (2)
    • Computer Science (42)
      • πŸ”’ Operating System (14)
      • πŸ“‘ Network (15)
      • πŸ’Ύ Database (8)
      • 🧩 Design Pattern (4)
      • πŸ”‘ Security (1)
    • Activities (12)
      • 🦁 λ©‹μŸμ΄μ‚¬μžμ²˜λŸΌ 9κΈ° (6)
      • πŸ’» SWλ§ˆμ—μŠ€νŠΈλ‘œ 13κΈ° (6)
    • Infra (1)
      • ☁️ AWS (1)
    • Languages (1)
      • πŸ’™ Python (1)
    • Backend (7)
      • πŸ”΅ Django (4)
      • 🟒 Node.js (3)
    • Ect. (8)
      • πŸ’¬ Talk (0)
      • πŸ—‚οΈ 개발직ꡰ μ·¨μ—… μ€€λΉ„μžλ£Œ (8)

λΈ”λ‘œκ·Έ 메뉴

  • ν™ˆ
  • νƒœκ·Έ
  • λ°©λͺ…둝

곡지사항

인기 κΈ€

졜근 λŒ“κΈ€

졜근 κΈ€

ν‹°μŠ€ν† λ¦¬

250x250
hELLO Β· Designed By μ •μƒμš°.
J1Yun

ZU-TECHLOG

[BOJ] λ°±μ€€ 7576번 ν† λ§ˆν†  - 파이썬(Python)
Algorithm/πŸ“˜ Baekjoon Judge

[BOJ] λ°±μ€€ 7576번 ν† λ§ˆν†  - 파이썬(Python)

728x90

문제

철수의 ν† λ§ˆν†  농μž₯μ—μ„œλŠ” ν† λ§ˆν† λ₯Ό λ³΄κ΄€ν•˜λŠ” 큰 μ°½κ³ λ₯Ό κ°€μ§€κ³  μžˆλ‹€. ν† λ§ˆν† λŠ” μ•„λž˜μ˜ κ·Έλ¦Όκ³Ό 같이 격자 λͺ¨μ–‘ μƒμžμ˜ 칸에 ν•˜λ‚˜μ”© λ„£μ–΄μ„œ 창고에 λ³΄κ΄€ν•œλ‹€.

창고에 λ³΄κ΄€λ˜λŠ” ν† λ§ˆν† λ“€ μ€‘μ—λŠ” 잘 읡은 것도 μžˆμ§€λ§Œ, 아직 읡지 μ•Šμ€ ν† λ§ˆν† λ“€λ„ μžˆμ„ 수 μžˆλ‹€. 보관 ν›„ ν•˜λ£¨κ°€ μ§€λ‚˜λ©΄, 읡은 ν† λ§ˆν† λ“€μ˜ μΈμ ‘ν•œ 곳에 μžˆλŠ” 읡지 μ•Šμ€ ν† λ§ˆν† λ“€μ€ 읡은 ν† λ§ˆν† μ˜ 영ν–₯을 λ°›μ•„ 읡게 λœλ‹€. ν•˜λ‚˜μ˜ ν† λ§ˆν† μ˜ μΈμ ‘ν•œ 곳은 μ™Όμͺ½, 였λ₯Έμͺ½, μ•ž, λ’€ λ„€ λ°©ν–₯에 μžˆλŠ” ν† λ§ˆν† λ₯Ό μ˜λ―Έν•œλ‹€. λŒ€κ°μ„  λ°©ν–₯에 μžˆλŠ” ν† λ§ˆν† λ“€μ—κ²ŒλŠ” 영ν–₯을 μ£Όμ§€ λͺ»ν•˜λ©°, ν† λ§ˆν† κ°€ 혼자 μ €μ ˆλ‘œ μ΅λŠ” κ²½μš°λŠ” μ—†λ‹€κ³  κ°€μ •ν•œλ‹€. μ² μˆ˜λŠ” 창고에 λ³΄κ΄€λœ ν† λ§ˆν† λ“€μ΄ 며칠이 μ§€λ‚˜λ©΄ λ‹€ 읡게 λ˜λŠ”μ§€, κ·Έ μ΅œμ†Œ 일수λ₯Ό μ•Œκ³  μ‹Άμ–΄ ν•œλ‹€.

ν† λ§ˆν† λ₯Ό 창고에 λ³΄κ΄€ν•˜λŠ” 격자λͺ¨μ–‘μ˜ μƒμžλ“€μ˜ 크기와 읡은 ν† λ§ˆν† λ“€κ³Ό 읡지 μ•Šμ€ ν† λ§ˆν† λ“€μ˜ 정보가 μ£Όμ–΄μ‘Œμ„ λ•Œ, 며칠이 μ§€λ‚˜λ©΄ ν† λ§ˆν† λ“€μ΄ λͺ¨λ‘ μ΅λŠ”μ§€, κ·Έ μ΅œμ†Œ 일수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜λΌ. 단, μƒμžμ˜ 일뢀 μΉΈμ—λŠ” ν† λ§ˆν† κ°€ λ“€μ–΄μžˆμ§€ μ•Šμ„ μˆ˜λ„ μžˆλ‹€.

μž…λ ₯

첫 μ€„μ—λŠ” μƒμžμ˜ 크기λ₯Ό λ‚˜νƒ€λ‚΄λŠ” 두 μ •μˆ˜ M,N이 μ£Όμ–΄μ§„λ‹€. M은 μƒμžμ˜ κ°€λ‘œ 칸의 수, N은 μƒμžμ˜ μ„Έλ‘œ 칸의 수λ₯Ό λ‚˜νƒ€λ‚Έλ‹€. 단, 2 ≤ M,N ≤ 1,000 이닀. λ‘˜μ§Έ μ€„λΆ€ν„°λŠ” ν•˜λ‚˜μ˜ μƒμžμ— μ €μž₯된 ν† λ§ˆν† λ“€μ˜ 정보가 μ£Όμ–΄μ§„λ‹€. 즉, λ‘˜μ§Έ 쀄뢀터 N개의 μ€„μ—λŠ” μƒμžμ— λ‹΄κΈ΄ ν† λ§ˆν† μ˜ 정보가 μ£Όμ–΄μ§„λ‹€. ν•˜λ‚˜μ˜ μ€„μ—λŠ” μƒμž κ°€λ‘œμ€„μ— λ“€μ–΄μžˆλŠ” ν† λ§ˆν† μ˜ μƒνƒœκ°€ M개의 μ •μˆ˜λ‘œ μ£Όμ–΄μ§„λ‹€. μ •μˆ˜ 1은 읡은 ν† λ§ˆν† , μ •μˆ˜ 0은 읡지 μ•Šμ€ ν† λ§ˆν† , μ •μˆ˜ -1은 ν† λ§ˆν† κ°€ λ“€μ–΄μžˆμ§€ μ•Šμ€ 칸을 λ‚˜νƒ€λ‚Έλ‹€.

ν† λ§ˆν† κ°€ ν•˜λ‚˜ 이상 μžˆλŠ” 경우만 μž…λ ₯으둜 μ£Όμ–΄μ§„λ‹€.

좜λ ₯

μ—¬λŸ¬λΆ„μ€ ν† λ§ˆν† κ°€ λͺ¨λ‘ 읡을 λ•ŒκΉŒμ§€μ˜ μ΅œμ†Œ λ‚ μ§œλ₯Ό 좜λ ₯ν•΄μ•Ό ν•œλ‹€. λ§Œμ•½, μ €μž₯될 λ•ŒλΆ€ν„° λͺ¨λ“  ν† λ§ˆν† κ°€ μ΅μ–΄μžˆλŠ” μƒνƒœμ΄λ©΄ 0을 좜λ ₯ν•΄μ•Ό ν•˜κ³ , ν† λ§ˆν† κ°€ λͺ¨λ‘ μ΅μ§€λŠ” λͺ»ν•˜λŠ” 상황이면 -1을 좜λ ₯ν•΄μ•Ό ν•œλ‹€.

 

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

 

7576번: ν† λ§ˆν† 

첫 μ€„μ—λŠ” μƒμžμ˜ 크기λ₯Ό λ‚˜νƒ€λ‚΄λŠ” 두 μ •μˆ˜ M,N이 μ£Όμ–΄μ§„λ‹€. M은 μƒμžμ˜ κ°€λ‘œ 칸의 수, N은 μƒμžμ˜ μ„Έλ‘œ 칸의 수λ₯Ό λ‚˜νƒ€λ‚Έλ‹€. 단, 2 ≤ M,N ≤ 1,000 이닀. λ‘˜μ§Έ μ€„λΆ€ν„°λŠ” ν•˜λ‚˜μ˜ μƒμžμ— μ €μž₯된 ν† λ§ˆν† 

www.acmicpc.net

 

πŸ’‘ 풀이 및 μ½”λ“œ

from collections import deque

m, n = map(int, input().split())
graph = []
queue = deque()

for i in range(n):
    temp = list(map(int, input().split()))
    graph.append(temp)
    for j in range(m):
        if temp[j] == 1:
            queue.append((i,j))
    
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    global queue
    result = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            if graph[nx][ny] == -1:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
                result = max(result, graph[nx][ny])
    return result -1

result = bfs()
for i in graph:
    if 0 in i:
        result = -1
        break
print(result)

 

μš°μ„ , κ·Έλž˜ν”„ 상 1의 μœ„μΉ˜λ₯Ό 큐에 λͺ¨λ‘ λ„£κ³  BFS μ•Œκ³ λ¦¬μ¦˜μ„ μ‚¬μš©ν•˜μ—¬ μΈμ ‘ν•œ λ…Έλ“œλ₯Ό 1μ”© 더해진 κ°’μœΌλ‘œ λŒ€μ²΄ν•˜μ˜€λ‹€. 이 λ•Œ, κ·Έ 값이 κ°€μž₯ 클 λ•Œλ₯Ό μ°Ύμ•„ -1을 ν•œ 수λ₯Ό ν† λ§ˆν† κ°€ λͺ¨λ‘ 읡기 μœ„ν•΄ μ§€λ‚˜κ°„ 일 수둜 ν‘œν˜„ν•˜μ˜€λ‹€. 이 λͺ¨λ“  과정을 μˆ˜ν–‰ν•œ ν›„ κ·Έλž˜ν”„μ— 0이 λ‚¨μ•„μžˆλ‹€λ©΄ λͺ¨λ“  ν† λ§ˆν† κ°€ 읡지 λͺ»ν•œ 것이기 λ•Œλ¬Έμ— -1을 좜λ ₯ν•΄μ£ΌλŠ” μ˜ˆμ™Έμ²˜λ¦¬λ„ ν•΄μ£Όμ—ˆλ‹€.

 

처음 이 문제λ₯Ό ν’€ λ•Œ, κ·Έλž˜ν”„ 상 1의 μœ„μΉ˜λ₯Ό 큐에 λͺ¨λ‘ λ„£λŠ” κ³Όμ •μ—μ„œ index ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•΄μ„œ 1의 μœ„μΉ˜λ₯Ό κΈ°λ‘ν–ˆλ‹€. κ·Έλž¬λ”λ‹ˆ 첫 쀄에 1이 두 κ°œμžˆλŠ” κ²½μš°μ— λŒ€ν•œ μ²˜λ¦¬κ°€ μ œλŒ€λ‘œ 이루어지지 μ•Šμ•˜λ‹€. 이 였λ₯˜λ₯Ό μ°Ύμ•„λ‚΄λŠ”λ°μ— κ½€λ‚˜ λ§Žμ€ μ‹œκ°„μ„ ν—ˆλΉ„ν–ˆλ‹€πŸ˜₯ μ•žμœΌλ‘œ index ν•¨μˆ˜λ₯Ό μ“°κΈ° μ „μ—λŠ” μ£Όμ˜κ°€ ν•„μš”ν•  것 κ°™λ‹€.

index ν•¨μˆ˜... ν•¨λΆ€λ‘œ μ“°μ§€ 말자!!πŸ‘Š

 

728x90

'Algorithm > πŸ“˜ Baekjoon Judge' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

[BOJ] λ°±μ€€ 2468번 μ•ˆμ „ μ˜μ—­ - 파이썬(Python)  (0) 2021.07.18
[BOJ] λ°±μ€€ 2583번 μ˜μ—­ κ΅¬ν•˜κΈ° - 파이썬(Python)  (0) 2021.07.17
[BOJ] λ°±μ€€ 1697번 μˆ¨λ°”κΌ­μ§ˆ - 파이썬(Python)  (0) 2021.07.15
[BOJ] λ°±μ€€ 2667번 λ‹¨μ§€λ²ˆν˜ΈλΆ™μ΄κΈ° - 파이썬(Python)  (0) 2021.07.15
[BOJ] λ°±μ€€ 2178번 미둜 탐색 - 파이썬(Python)  (0) 2021.07.15
    'Algorithm/πŸ“˜ Baekjoon Judge' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ 글이닀
    • [BOJ] λ°±μ€€ 2583번 μ˜μ—­ κ΅¬ν•˜κΈ° - 파이썬(Python)
    • [BOJ] λ°±μ€€ 1697번 μˆ¨λ°”κΌ­μ§ˆ - 파이썬(Python)
    • [BOJ] λ°±μ€€ 2667번 λ‹¨μ§€λ²ˆν˜ΈλΆ™μ΄κΈ° - 파이썬(Python)
    • [BOJ] λ°±μ€€ 2178번 미둜 탐색 - 파이썬(Python)
    J1Yun
    J1Yun
    개발 κ΄€λ ¨ 기술 및 곡뢀 λ‚΄μš© 기둝μž₯

    ν‹°μŠ€ν† λ¦¬νˆ΄λ°”