
๐ ๋ฌธ์
๋น์ฐํ ์ด์ผ๊ธฐ์ง๋ง, ์ฑ๊ณต์ผ๋ก ๊ฐ๋ ๊ธธ์ด ํญ์ ํํํ์ง๋ง์ ์๋ค. ์จ๊ฐ ์ฅ์ ๋ฌผ์ด ๊ฐ๋ํ๊ณ , ์ฅ์ ๋ฌผ์ ๋งํ์ ์ฃผ์ ์์ ์๋ ์๋ค. ๊ทธ๋์ ๊ทธ ์ฅ์ ๋ฌผ์ ํญํํ๋ ค๊ณ ํ๋ค.
์ฑ๊ณต์ผ๋ก ๊ฐ๋ ๊ธธ์ NรM๊ฒฉ์ ์์ ๋์ฌ ์๋ค. ์ฑ๊ณต์ผ๋ก ๊ฐ๋ ค๋ฉด ๋งจ ์ผ์ชฝ ์ ์นธ์์ ์์ํ์ฌ ์ฅ์ ๋ฌผ์ด ์๋ ์ํ์ข์ฐ๋ก ์ธ์ ํ ์นธ์ ๋ฐ์ผ๋ฉด์ ๋งจ ์ค๋ฅธ์ชฝ ์๋ ์นธ์ ๋์ฐฉํด์ผ ํ๋ค. ํ ๋ฒ์ ํญํ ์์ ์ผ๋ก DรD ๊ฒฉ์ ๋ด์ ์๋ ๋ชจ๋ ์ฅ์ ๋ฌผ์ ์์จ ์ ์๋ค. ํ์ง๋ง ์ธ์์ ๊ณต์ง๋ ์๋ ๋ฒ. ํญํ ์์ ์๋ ํฐ ํ์ด ๋ค๊ธฐ ๋๋ฌธ์, ์ฑ๊ณต์ผ๋ก ๊ฐ๋ ค๋ฉด ์ต์ ๋ช ๋ฒ์ ํญํ ์์ ์ด ํ์ํ์ง ์๊ณ ์ถ๋ค.
๐์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์ ๊ฒฉ์์ ํ์ ๊ฐ์ N, ์ด์ ๊ฐ์ M, ํญํ์ ๋ฒ์ D๊ฐ ์ฃผ์ด์ง๋ค(D โค N, M โค 500, 1 โค D โค 100).
๊ทธ ๋ค์ N๊ฐ์ ์ค์ ๊ฒฉ์์ ๊ฐ ํ์ ๋ํ๋ด๋ ๊ธธ์ด M์ ๋ฌธ์์ด์ด ์ฃผ์ด์ง๋ค. โ.โ์ ์ฅ์ ๋ฌผ์ด ์๋ ์นธ, โ#โ์ ์ฅ์ ๋ฌผ์ด ์๋ ์นธ์ด๋ค. ์ถ๋ฐ ์ง์ ๊ณผ ์ฑ๊ณต์๋ ์ฅ์ ๋ฌผ์ด ์๋ค.
๐์ถ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์ ํญํ ์์ ์ ์ต์ ํ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ง ๋ฌธ์ ์ ๊ทผ
N * M ๋ณด๋์์ (0, 0) ์์ ์์ํ์ฌ (N - 1, M - 1) ๊น์ง ๋๋ฌํ๊ธฐ ์ํด์ ์ต์ ๋ช ๋ฒ ๋ฒฝ์ ํญํํด์ผ ํ๋๊ฐ? ๋ฅผ ๊ตฌํด์ผ ํ๋ ๋ฌธ์ ์ด๋ค. ๋ฒฝ์ ํญํํ ๋๋ ํ ์นธ๋ง ๋ถ์ ์ ์๋๊ฒ ์๋๋ผ D * D ๋ฒ์๋ฅผ ํญํ์ํจ๋ค.
'๊ทธ๋ํ', '์ต์', ๋ผ๋ ํค์๋๊ฐ ๋ฑ์ฅํ์ฌ ๋ฐ์ดํฌ์คํธ๋ผ์ธ๊ฐ ํ๊ณ ๊ทธ์ชฝ์ผ๋ก ๋ฐฉํฅ์ ํ์๋ค.
์ฌ๋ ๋ฐ์ดํฌ์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ์ฒ๋ผ ํญํํ ํ์๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๋ฉฐ ๊ทธ๋ํ๋ฅผ ํ์ํ๋, ์ฅ์ ๋ฌผ์ ๋ง๋๋ฉด ๊ทธ๊ณณ์ ํญํํด์ฃผ๋ ๋ฐฉ์์ ์๊ฐํ์๋ค. ์ฒ์์๋ ์ฅ์ ๋ฌผ์ ๋ง๋๋ฉด ํด๋น ์ฅ์ ๋ฌผ์ ์ ๊ฑฐํ๊ธฐ ์ํด D * D ๋ฐ๋ณต ํ๋ฉด์ ํญํ๋ ๋ณด๋๋ฅผ ์ ๋ฐ์ดํธ ํด์ฃผ์๋ค.
ํ์ง๋ง ์ด๋ ๊ฒ ๊ตฌํํ๋ค๋ฉด N * M * D^2๋ก ์ ํ ์๊ฐ 2์ด ์์ ํต๊ณผํ์ง ๋ชปํ๋ค. (500 * 500 * 100^2 = 2,500,000,000)
๊ทธ๋ผ N * M * D๋ก ํด๊ฒฐํด์ผ ํ๋ ๋ฌธ์ ๋ผ๋ ๊ฒ์ ์ ์ ์๋ค.
๐ ๋ฌธ์ ํ์ด
๊ทธ๋ผ D * D ๋ฐ๋ณตํ์ง ์์ผ๋ฉด์ ์ด๋ป๊ฒ ํญํ๋ฅผ ํ ์ ์์๊น. ์์ด๋์ด๋ ์ง์ ํญํํ์ง ์๊ณ ์ํํ๋ ๊ฒ์ด๋ค.
N = 9, M = 9, D = 3 ์ผ๋, ํ์ฌ (4, 4)์ ์์นํ์๋ค๊ณ ๊ฐ์ ํ์.

D = 3์ด๋ ํ๋ฒ ํญํํ๋ฉด ์๋ ๊ทธ๋ฆผ์ฒ๋ผ D * D ๋ฒ์์ ํจ๊ณผ๊ฐ ์์ ๊ฒ์ด๋ค.

์ ์์น์์ ํญํ์์ผ์ ์ด๋ํ ์ ์๋ ๊ฒ์ ํ์ ํด๋ณด๋ฉด ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ๋ค.


์ ๋ฆฌํ์๋ฉด ์๋ ์ฃผํฉ์ ๋ถ๋ถ์ผ๋ก ์น ํด์ ธ์๋ ๋ถ๋ถ์ ํ์ฌ ์์น (4, 4)์์ ํญํ ํ๋ฒ ํฐ๋จ๋ ค์ ์ด๋ํ ์ ์๋ ๋ฒ์์ด๋ค.

D * D ๋๋ฉด์ ๋ณด๋ ์ ๋ฐ์ดํธ ํ ํ์ ์์ด ํ์ฌ ์์น์์ ํญํ ํฐ์ง๊ณ ๋ ํ์ ์์น๋ก ์ํํ๋ฉด ๋๋ค!
๋ฌผ๋ก ํ์ฌ ์์น์์ ์ํ์ข์ฐ๋ก๋ ํ์์ ํ๋ค.
์ฃผํฉ์ ๋ฒ์ ์์ ์๋ ๊ณณ์ ํ์ ๋ชปํ๋๊ฑฐ ์๋๊ฐ? ํ๋ ์๋ฌธ์ด ๋ค ์ ์์ง๋ง, ํญํ์ ๋ ๋จ๋ฆฐ ํ์๋ก ์ ๋ ฌํด์ ํ์ํ๊ธฐ ๋๋ฌธ์ ์ฃผํฉ์ ๋ฒ์ ์์ด ๋ชจ๋ ์ฅ์ ๋ฌผ์ด ์๋ค๋ฉด ๋น ์ง์์ด ํ์ํ๊ฒ ๋๊ณ , ์ฅ์ ๋ฌผ์ด ์๋ค๋ฉด, ํ์ฌ ์์น๊ฐ ์๋ ๋ค๋ฅธ ์์น์์ ์ธ์ ๊ฐ ๋ฐฉ๋ฌธํ๊ฒ ๋์ด์๋ค.
๊ทธ๋ผ ์ด์ ๋ฐ์ดํฌ์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๋ฉด ๋ ๊น?
๋ฌผ๋ก ๋ฐ์ดํฌ์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก๋ ํ ์ ์๋ค! ํ์ง๋ง ์ข ๋ ๊ด์ฐฐํด๋ณด๋ฉด, ํ์ฌ ์์น์์ ์ํ์ข์ฐ๋ก ํ์ํ ๋ ์ฅ์ ๋ฌผ์ด ์๋ค๋ฉด ํญํ ์นด์ดํธ ์ฆ๊ฐ ์์ด ์ด๋ ๊ฐ๋ฅํ๊ณ , D ๋งํผ ์ํ ๋ธ ๋์๋ ํญํ ์นด์ดํธ 1 ์ฆ๊ฐํ๋ฉด์ ์ด๋ํ๋ ๊ฒ์ ์ ์ ์๋ค.
(0๊ณผ 1... 0๊ณผ 1์ ๋ฏธ๋ก๊ฐ ๋ณด์ฌ)
๊ทธ๋ ๋ค 0 - 1 bfs๋ก๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค. ์ํ์ข์ฐ ํ์ํ ๋์๋ ํ ์ผ์ชฝ์ ์ถ๊ฐํด์ฃผ๊ณ , D ์ํ ๋ธ ๋์๋ ํ ์ค๋ฅธ์ชฝ์ ์ถ๊ฐํด์ฃผ๋ฉฐ ํ์ํ๋ฉด ๋ ํจ์จ์ ์ธ ์๊ฐ ๋ณต์ก๋๋ก ๋ฌธ์ ๊ฐ ํด๊ฒฐ ๊ฐ๋ฅํ๋ค.
๐ป ์ฝ๋
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | from collections import deque import sys input = sys.stdin.readline n,m,d = map(int,input().split()) board = [list(input().rstrip()) for _ in range(n)] bomb = [[float('inf')] * m for _ in range(n)] bomb[0][0] = 0 queue = deque([(0,0,0)]) # cnt, y, x, board while queue: cnt, y, x = queue.popleft() if y==n-1 and x==m-1: break if bomb[y][x] < cnt: continue # ์ํ์ข์ฐ ํ์ for dy,dx in ((0,-1), (0,1), (1,0), (-1,0)): ny,nx = y + dy, x + dx if ny < 0 or nx < 0 or ny >= n or nx >= m: continue if board[ny][nx] == '.' and bomb[y][x] < bomb[ny][nx]: bomb[ny][nx] = bomb[y][x] queue.appendleft((bomb[ny][nx], ny, nx)) # d ์ํ ๋ฐ๋ฉฐ ํ์ for ddy,ddx in ((0,d), (0,-d), (-d,0), (d,0)): for i in range(-d+1, d): ny = y + ddy + (i if ddy == 0 else 0) nx = x + ddx + (i if ddx == 0 else 0) # ๋ฒ์ ๋์ด๊ฐ ๊ฒฝ์ฐ ๊ฒฝ๊ณ๋ก ์ค์ if ny < 0 or nx < 0 or ny >= n or nx >=m: ny = max(0, ny) nx = max(0, nx) ny = min(ny, n - 1) nx = min(nx, m - 1) if bomb[y][x] + 1 < bomb[ny][nx]: bomb[ny][nx] = bomb[y][x] + 1 queue.append((bomb[ny][nx], ny, nx)) print(bomb[n-1][m-1]) | cs |
๐ญ ์ํ์ฐฉ์ค

0-1 bfs: 1436 ms
๋ฐ์ดํฌ์คํธ๋ผ: 1768 ms
๐ ๋ฌธ์ ๋งํฌ
'Problem Solving > ๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 16877๋ฒ: ํ๋ฒ (0) | 2025.03.30 |
---|---|
[๋ฐฑ์ค] 5015๋ฒ: ls (1) | 2024.11.16 |
[๋ฐฑ์ค] 28357๋ฒ: ์ฌํ ๋๋ ์ฃผ๊ธฐ (1) | 2023.10.08 |
[๋ฐฑ์ค] 5942๋ฒ: Big Macs Around the World (0) | 2023.09.18 |
[๋ฐฑ์ค] 20560๋ฒ: ๋ง์ง ํ๋ฐฉ (1) | 2023.09.01 |