https://www.acmicpc.net/problem/2178
2178๋ฒ: ๋ฏธ๋ก ํ์
์ฒซ์งธ ์ค์ ๋ ์ ์ N, M(2 ≤ N, M ≤ 100)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ M๊ฐ์ ์ ์๋ก ๋ฏธ๋ก๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ๊ฐ์ ์๋ค์ ๋ถ์ด์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค.
www.acmicpc.net
๋ฌธ์
N×Mํฌ๊ธฐ์ ๋ฐฐ์ด๋ก ํํ๋๋ ๋ฏธ๋ก๊ฐ ์๋ค.
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
๋ฏธ๋ก์์ 1์ ์ด๋ํ ์ ์๋ ์นธ์ ๋ํ๋ด๊ณ , 0์ ์ด๋ํ ์ ์๋ ์นธ์ ๋ํ๋ธ๋ค. ์ด๋ฌํ ๋ฏธ๋ก๊ฐ ์ฃผ์ด์ก์ ๋, (1, 1)์์ ์ถ๋ฐํ์ฌ (N, M)์ ์์น๋ก ์ด๋ํ ๋ ์ง๋์ผ ํ๋ ์ต์์ ์นธ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ํ ์นธ์์ ๋ค๋ฅธ ์นธ์ผ๋ก ์ด๋ํ ๋, ์๋ก ์ธ์ ํ ์นธ์ผ๋ก๋ง ์ด๋ํ ์ ์๋ค.
์์ ์์์๋ 15์นธ์ ์ง๋์ผ (N, M)์ ์์น๋ก ์ด๋ํ ์ ์๋ค. ์นธ์ ์ ๋์๋ ์์ ์์น์ ๋์ฐฉ ์์น๋ ํฌํจํ๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ ์ ์ N, M(2 ≤ N, M ≤ 100)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ M๊ฐ์ ์ ์๋ก ๋ฏธ๋ก๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ๊ฐ์ ์๋ค์ ๋ถ์ด์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ง๋์ผ ํ๋ ์ต์์ ์นธ ์๋ฅผ ์ถ๋ ฅํ๋ค. ํญ์ ๋์ฐฉ์์น๋ก ์ด๋ํ ์ ์๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค.
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
4 6
101111
101010
101011
111011
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
15
์์ ์ ๋ ฅ 2 ๋ณต์ฌ
4 6
110110
110110
111111
111101
์์ ์ถ๋ ฅ 2 ๋ณต์ฌ
9
ํ์ด
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input().rstrip())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
queue.append((nx,ny))
graph[nx][ny] = graph[x][y] + 1
return graph[n-1][m-1]
print(bfs(0,0))
๐ ํ์ด
1. graph[0][0]๋ถํฐ (์ค์ ์์น๋ (1, 1)) bfs๋ฅผ ์ด์ฉํด ๋, ์, ๋จ, ๋ถ์ ๊ฒ์ฌํ์ฌ ์ด๋ํ์ ๋ 1์ธ ๊ฐ์ ์ฐพ๋๋ค.
-> ๊ฐ์ด 1 ์ด์ด์ผ ์ด๋ํ ์ ์๊ธฐ ๋๋ฌธ์
2. ๋ง์ฝ 1์ด๋ผ๋ฉด ๊ทธ ์ ๊ฐ์ +1์ ํ์ฌ ์ด๋ํ ๋ ์ง๋์ผ ํ๋ ์ต์ ์นธ ์๋ฅผ ๋ํด์ค๋ค.
3. ์ด๋ ๊ฒ ์ญ ๊ฒ์ฌ ํ๋ค๋ณด๋ฉด ๋ง์ง๋ง graph[n - 1][m - 1]์๋ ์ต์ ์นธ ์์ ์ต์ข
๊ฐ์ด ๋ค์ด๊ฐ๊ฒ ๋๋ค.
โป ํ์๋ ํญ์ ์ด๋ฐ์์ผ๋ก x์ถ, y์ถ์ผ๋ก ์ค๋ช ํ๋ค

๐ ์์ด๋์ด
1. ์, ํ, ์ข, ์ฐ๋ฅผ ๋ํ๋ด๊ธฐ ์ํด์ dx, dy๊ฐ์ ์ด์ฉํ๋ค
์ : x์ถ์ผ๋ก -1, y๊ฐ์ ๊ทธ๋๋ก (์๋ก ์ฌ๋ผ๊ฐ๋๊น)
ํ : x์ถ์ผ๋ก +1, y๊ฐ์ ๊ทธ๋๋ก (์๋๋ก ๋ด๋ ค๊ฐ๋๊น)
์ข : x๊ฐ์ ๊ทธ๋๋ก, y์ถ์ผ๋ก -1์ ๊ทธ๋๋ก
์ฐ : x๊ฐ์ ๊ทธ๋๋ก, y์ถ์ผ๋ก +1์ ๊ทธ๋๋ก
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
2. ๋ฐ๋ณต๋ฌธ์ผ๋ก ์ฌ๋ฌ ์ค์ ์ ๋ ฅ๋ฐ์๋ sys.stdin.readline()์ ์ฌ์ฉํ๋ค
( ์ฌ์ค ํ๋ก๊ทธ๋๋จธ์ค์๋ ์ ๋ ฅ๊ฐ์ ์ ๋ ฅ๋ฐ์ง ์๊ธฐ ๋๋ฌธ์ ์ธ ์ผ์ด ์์ ์๋ ์๋ค )
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
3. ๋ฑ ์ฌ์ฉํ๊ธฐ
from collections import deque
def bfs(x,y):
queue = deque()
queue.append((x,y))
4. ์ ๋ ฅ๋ฐ์๋๋ rstrip์ผ๋ก ์ํฐ๊ฐ ์ ๊ฑฐ
for i in range(n):
graph.append(list(map(int, input().rstrip())))
โ๏ธ5. ํ์ ์ผ๋จ ๋ฃ๊ณ ์์ํ๊ณ , ํ์ ์๋ ๊ฐ์ด ๋ชจ๋ pop๋ ๋๊น์ง ์งํ๋๋ค
nx์ ny๋ชจ๋ ๋ฒ์ ์์ด๊ณ ๊ฐ์ด ๊ฒฐ์ ์ ์ผ๋ก 1์ผ๋๋ง ๊ฐ์ ์ฆ๊ฐ์ํค๊ณ ํ์ ๋ฃ๋๋ค
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
queue.append((nx,ny))
graph[nx][ny] = graph[x][y] + 1
return graph[n-1][m-1]
'Algorithm๐ค > ๋ฐฑ์ค BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| [๋ฐฑํธ๋ํน] 9663๋ฒ N-Queen - ํ์ด์ฌ(Python) (0) | 2023.06.05 |
|---|---|
| [๋ฐฑ์ค] 15649๋ฒ N๊ณผ M(1) / ํ์ด์ฌ(python) (0) | 2023.06.01 |
| [DP๐ฑ] ๊ฑฐ์ค๋ฆ๋ ๊ฑฐ์ฌ๋ฌ์ฃผ๊ธฐ, ๋์ ๊ฐฏ์ ์ต์๋ก ์ฃผ๊ธฐ (2) | 2023.05.21 |
| [DP๐ฑ] ๊ท์ฌ์ด ์์ฅ๐์ ๐ง์น์ฆ๋จน๊ธฐ! ๐ (0) | 2023.05.21 |
| [DP๐ฑ] 9095๋ฒ: 1, 2, 3 ๋ํ๊ธฐ - Python (0) | 2023.05.21 |