์šฐ๊ทœ์ด์ธ์šฐ์œค
Eager To Learn ๐ŸŒŒ
์šฐ๊ทœ์ด์ธ์šฐ์œค
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ๐Ÿก ํ™ˆ
  • ๐Ÿš€ ๊นƒํ—ˆ๋ธŒ
  • โ›… ํƒœ๊ทธ ํด๋ผ์šฐ๋“œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (217)
    • ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป PS (170)
      • JAVA (82)
      • MYSQL (1)
      • Docker (2)
      • PYTHON (24)
      • LeetCode 150 (39)
      • Algorithm ๊ธฐ๋ฒ• (1)
      • ๋ฐ”ํ‚น๋… (21)
    • ๋ธ”๋กœ๊ทธ ์ด์‚ฌ (0)
    • Error (1)
    • CS (15)
      • DataBase (2)
      • OS (7)
      • Network (1)
      • Spring (1)
      • ์ž๋ฃŒ๊ตฌ์กฐ (3)
      • Java (1)
    • Learned (7)
      • Spring (7)
    • ๊ฐœ๋ฐœ์„œ์  (15)
      • ๊ฐ€์ƒ ๋ฉด์ ‘ ์‚ฌ๋ก€๋กœ ๋ฐฐ์šฐ๋Š” ๋Œ€๊ทœ๋ชจ ์‹œ์Šคํ…œ ์„ค๊ณ„ ๊ธฐ์ดˆ (1)
      • ์˜ค๋ธŒ์ ํŠธ - ์กฐ์˜ํ˜ธ (7)
      • ์นœ์ ˆํ•œ SQL ํŠœ๋‹ (7)
    • ํšŒ๊ณ  (2)
hELLO ยท Designed By ์ •์ƒ์šฐ.
์šฐ๊ทœ์ด์ธ์šฐ์œค

Eager To Learn ๐ŸŒŒ

๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป PS/PYTHON

[ํŒŒ์ด์ฌ PYTHON] ๋ฐฑ์ค€ 2146๋ฒˆ ใ€๋‹ค๋ฆฌ ๋งŒ๋“ค๊ธฐใ€‘

2023. 3. 10. 11:53


import sys
from collections import deque

N = int(input())
_map = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]


# ์„ฌ ๋ผ๋ฒจ๋ง
def labeling(label):
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr = dr[i] + r
            nc = dc[i] + c
            if 0 <= nr < N and 0 <= nc < N and _map[nr][nc] == 1:
                _map[nr][nc] = label
                queue.append([nr, nc])


label = -1
queue = deque([])

for r in range(N):
    for c in range(N):
        if _map[r][c] == 1:
            _map[r][c] = label
            queue.append([r, c])
            labeling(label)
            label -= 1

# ์œก์ง€ ์ขŒํ‘œ ๊ตฌํ•˜๊ธฐ

for r in range(N):
    for c in range(N):
        if _map[r][c] < 0:
            queue.append([r, c])

ans = 1e9
distanceMap = [[0] * N for _ in range(N)]


def bfs():
    global ans
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr = dr[i] + r
            nc = dc[i] + c
            if 0 <= nr < N and 0 <= nc < N:
                # ๊ตฌํ•œ ์œก์ง€ ์ขŒํ‘œ๊ฐ€ ๋ฐ”๋‹ค์™€ ์ธ์ ‘ํ•œ ๊ฒฝ์šฐ์—๋งŒ ๋กœ์ง ์‹คํ–‰
                if _map[nr][nc] == 0:
                    queue.append([nr, nc])
                    _map[nr][nc] = _map[r][c]
                    distanceMap[nr][nc] = distanceMap[r][c] + 1
                # ๋‹ค๋ฅธ ์œก์ง€์—์„œ ์ถœ๋ฐœํ•œ ์˜์—ญ๊ณผ ๋งŒ๋‚œ ๊ฒฝ์šฐ ( ๋‹ค๋ฅธ ์œก์ง€์—์„œ ์ถœ๋ฐœํ•œ ์˜์—ญ์€ ์Œ์ˆ˜๋กœ ์ž…๋ ฅ๋˜๋ฏ€๋กœ)
                elif _map[nr][nc] < 0 and _map[nr][nc] != _map[r][c]:
                    ans = min(ans,distanceMap[nr][nc]+distanceMap[r][c])


bfs()
print(ans)

 

๋ฌธ์ œ ์ ‘๊ทผ ๋ฐฉ๋ฒ•

1. bfs ํƒ์ƒ‰์„ ๊ตฌํ˜„ํ•œ labeling() ํ•จ์ˆ˜๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์„ฌ๋งˆ๋‹ค ์Œ์ˆ˜๋กœ ๋ผ๋ฒจ๋ง์„ ํ•œ๋‹ค.

2. ์Œ์ˆ˜๋กœ ๋ผ๋ฒจ๋ง ํ–ˆ์œผ๋ฏ€๋กœ ๋งต ์ „์ฒด๋ฅผ ํƒ์ƒ‰ํ•˜๋ฉด์„œ ๊ฐ’์ด ์Œ์ˆ˜์ธ ์ขŒํ‘œ๋“ค์„ ๋ชจ๋‘ queue์— ๊ธฐ๋กํ•œ๋‹ค.

3. ์œก์ง€ ์ขŒํ‘œ๋กœ bfs()๋ฅผ ํ•˜๋Š”๋ฐ, ์ด๋™ํ•œ ๊ฐ’์ด 0์ธ๊ฒฝ์šฐ์—๋งŒ ๋‹ค์Œ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•œ๋‹ค.

0์ด์—ˆ๋˜ ์ขŒํ‘œ(๋ฐ”๋‹ค)์—๋Š”, _map์— ์œก์ง€ ๋ฒˆํ˜ธ๋ฅผ ๊ธฐ๋กํ•˜๊ณ  distanceMap์—๋Š” ๊ฑฐ๋ฆฌ๋ฅผ ๊ธฐ๋กํ•œ๋‹ค.

4. ๋งŒ์•ฝ ํƒ์ƒ‰ ์ค‘์— ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•œ _map์ขŒํ‘œ์™€ ํƒ์ƒ‰์„ ํ•  _map ์ขŒํ‘œ ๊ฐ’์ด ๋‹ค๋ฅด๋‹ค๋Š” ๊ฒƒ์€ 
๊ฐ๊ฐ ๋‹ค๋ฅธ ์œก์ง€์—์„œ ์ถœ๋ฐœํ•œ ํƒ์ƒ‰ ์ขŒํ‘œ๋ผ๋Š” ๋œป์ด๋ฏ€๋กœ ๊ฑฐ๋ฆฌ๋ฅผ ๊ธฐ๋กํ•œ๋‹ค.

5. ์ตœ์†Œ ๊ฑฐ๋ฆฌ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

    '๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป PS/PYTHON' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [ํŒŒ์ด์ฌ PYTHON · ์ž๋ฐ” JAVA] LeetCodeใ€Best Time to Buy and Sell Stockใ€‘
    • [ํŒŒ์ด์ฌ PYTHON · ์ž๋ฐ” JAVA] LeetCodeใ€Two sumใ€‘
    • [ํŒŒ์ด์ฌ PYTHON] ๋ฐฑ์ค€ 2638๋ฒˆ ใ€์น˜์ฆˆใ€‘
    • [ํŒŒ์ด์ฌ PYTHON] ๋ฐฑ์ค€ 16236๋ฒˆ ใ€์•„๊ธฐ ์ƒ์–ดใ€‘
    ์šฐ๊ทœ์ด์ธ์šฐ์œค
    ์šฐ๊ทœ์ด์ธ์šฐ์œค
    ๊ฐœ๋ฐœ์ž ๊ฟˆ๋‚˜๋ฌด

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”