We will find a way, we always have.

-interstellar

Problem Solving/๋ฐฑ์ค€

[๋ฐฑ์ค€] 15944๋ฒˆ: ์„ฑ๊ณต

Redddy 2024. 11. 7. 21:48

๐Ÿ”ˆ ๋ฌธ์ œ

๋‹น์—ฐํ•œ ์ด์•ผ๊ธฐ์ง€๋งŒ, ์„ฑ๊ณต์œผ๋กœ ๊ฐ€๋Š” ๊ธธ์ด ํ•ญ์ƒ ํ‰ํƒ„ํ•˜์ง€๋งŒ์€ ์•Š๋‹ค. ์˜จ๊ฐ– ์žฅ์• ๋ฌผ์ด ๊ฐ€๋“ํ•˜๊ณ , ์žฅ์• ๋ฌผ์— ๋ง‰ํ˜€์„œ ์ฃผ์ €์•‰์„ ์ˆ˜๋„ ์žˆ๋‹ค. ๊ทธ๋ž˜์„œ ๊ทธ ์žฅ์• ๋ฌผ์„ ํญํŒŒํ•˜๋ ค๊ณ  ํ•œ๋‹ค.
์„ฑ๊ณต์œผ๋กœ ๊ฐ€๋Š” ๊ธธ์€ 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)์— ์œ„์น˜ํ–ˆ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž.

(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

 

๐Ÿ”— ๋ฌธ์ œ๋งํฌ