hugDog
Android DevLog
hugDog
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๐Ÿ™Œ Hello? (162)
    • ๐Ÿงฉ์•ˆ๋“œ๋กœ์ด๋“œ (12)
      • ๊ฐœ๋… ์ •๋ฆฌ (5)
      • ๋ฒ„๊ทธ ํ•ด๊ฒฐ (4)
      • ๊ธฐํƒ€ (3)
    • ๐Ÿ”์•Œ๊ณ ๋ฆฌ์ฆ˜ (54)
      • ๊ฐœ๋… (0)
      • ๋ฐฑ์ค€ (48)
      • ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค (6)
    • ๐Ÿ“„๊ฐœ๋ฐœ ์ผ์ง€ (0)
      • FINPO (0)
    • ๐Ÿ”คํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด (71)
      • C++ ์ •๋ฆฌ (49)
      • C++๊ธฐ์ดˆํ”Œ๋Ÿฌ์Šค ์—ฐ์Šต๋ฌธ์ œ (20)
      • Kotlin (2)
    • โญProject (1)
    • ๐ŸšดTIL (13)
      • Clean Code (13)
    • ๐Ÿšฉ๊ธฐํƒ€ (9)
      • ๋ชฉํ‘œ (6)
      • ์ผ์ƒ (3)
      • ๋ฌธ์„œ (0)

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

hELLO ยท Designed By ์ •์ƒ์šฐ.
hugDog

Android DevLog

[Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 2146๋ฒˆ: ๋‹ค๋ฆฌ ๋งŒ๋“ค๊ธฐ
๐Ÿ”์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฐฑ์ค€

[Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 2146๋ฒˆ: ๋‹ค๋ฆฌ ๋งŒ๋“ค๊ธฐ

2022. 1. 8. 16:05
728x90

๋ฌธ์ œ

 

ํ’€์ด

์ž…๋ ฅ

import sys
from collections import deque

imput = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

dir = ((0, 1), (0, -1), (1, 0), (-1, 0))

 

์„ฌ์„ ๋‚˜๋ˆ„๋Š” ๊ณผ์ •

0์ด ์•„๋‹Œ ์ขŒํ‘œ๋ฅผ ๋ฐœ๊ฒฌํ•œ ๊ฒฝ์šฐ ๊ทธ ์ขŒํ‘œ์™€ ์—ฐ๊ฒฐ๋œ ๊ฐ’์„ ์ „๋ถ€ mark๋กœ ๋ฐ”๊พผ๋‹ค.

mark = 1
for i in range(n):
    for j in range(n):
        if graph[i][j] and not visited[i][j]:
            marking(i, j, mark)
            mark += 1

 

marking ํ•จ์ˆ˜

๊ฐ ์„ฌ์˜ ๋ฒˆํ˜ธ๋ฅผ ๋ฐ”๊ฟ”์คŒ

def marking(y, x, mark):
    q = deque()
    q.append((y, x))
    graph[y][x] = mark
    visited[y][x] = True
    while q:
        i, j = q.popleft()
        for dy, dx in dir:
            ni, nj = i + dy, j + dx
            if condition(ni, nj) or not graph[ni][nj]:   continue
            graph[ni][nj] = mark
            visited[ni][nj] = True
            q.append((ni, nj))

 

condition ํ•จ์ˆ˜

def condition(ni, nj):
    return ni < 0 or ni >= n or nj < 0 or nj >= n or visited[ni][nj]

 

getDist ํ•จ์ˆ˜

๊ฐ ์ขŒํ‘œ์—์„œ ๋‹ค๋ฅธ ์„ฌ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•œ๋‹ค.

def getDist(y, x, now):
    q = deque()
    q.append((y, x, 0))
    while q:
        i, j, cnt = q.popleft()
        if graph[i][j] != 0 and graph[i][j] != now:
            return cnt
        for dy, dx in dir:
            ni, nj = i + dy, j + dx
            if condition(ni, nj) or graph[ni][nj] == now:   continue
            visited[ni][nj] = True
            q.append((ni, nj, cnt + 1))
    return 2000

 

๊ฐ ์ขŒํ‘œ์—์„œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์„ฌ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•œ๋‹ค.

ans = 2000
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            visited = [[False] * n for _ in range(n)]
            ans = min(ans, getDist(i, j, graph[i][j]))

 

์ฝ”๋“œ

import sys
from collections import deque

imput = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

dir = ((0, 1), (0, -1), (1, 0), (-1, 0))

def condition(ni, nj):
    return ni < 0 or ni >= n or nj < 0 or nj >= n or visited[ni][nj]

def marking(y, x, mark):
    q = deque()
    q.append((y, x))
    graph[y][x] = mark
    visited[y][x] = True
    while q:
        i, j = q.popleft()
        for dy, dx in dir:
            ni, nj = i + dy, j + dx
            if condition(ni, nj) or not graph[ni][nj]:   continue
            graph[ni][nj] = mark
            visited[ni][nj] = True
            q.append((ni, nj))

def getDist(y, x, now):
    q = deque()
    q.append((y, x, 0))
    while q:
        i, j, cnt = q.popleft()
        if graph[i][j] != 0 and graph[i][j] != now:
            return cnt
        for dy, dx in dir:
            ni, nj = i + dy, j + dx
            if condition(ni, nj) or graph[ni][nj] == now:   continue
            visited[ni][nj] = True
            q.append((ni, nj, cnt + 1))
    return 2000
            

mark = 1
for i in range(n):
    for j in range(n):
        if graph[i][j] and not visited[i][j]:
            marking(i, j, mark)
            mark += 1

ans = 2000
for i in range(n):
    for j in range(n):
        if graph[i][j] != 0:
            visited = [[False] * n for _ in range(n)]
            ans = min(ans, getDist(i, j, graph[i][j]))
        
print(ans - 1)

 

๋งˆ๋ฌด๋ฆฌ

๊ณจ๋“œ 3 bfs ๋ฌธ์ œ๋Š” ์ด์ œ ์กธ์—…ํ•ด๋„ ๋  ๋“ฏ์‹ถ๋‹ค.

 

728x90
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ (์ƒˆ์ฐฝ์—ด๋ฆผ)
    '๐Ÿ”์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฐฑ์ค€' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 11578๋ฒˆ: ํŒ€์› ๋ชจ์ง‘
    • [Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 17472๋ฒˆ: ๋‹ค๋ฆฌ ๋งŒ๋“ค๊ธฐ 2
    • [Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 1726๋ฒˆ: ๋กœ๋ด‡
    • [Python/ํŒŒ์ด์ฌ] ๋ฐฑ์ค€ 3055๋ฒˆ: ํƒˆ์ถœ
    hugDog
    hugDog
    ์•ˆ๋“œ๋กœ์ด๋“œ ๊ณต๋ถ€ ์ค‘์ธ ํ•™์ƒ์ž…๋‹ˆ๋‹ค!

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