๐ ๋ฏธ๋ก ํ์
๋ฐฑ์ค Class3 Silver1
solved_ac[Class3] ๋ฏธ๋ก ํ์
๋ฌธ์
NรMํฌ๊ธฐ์ ๋ฐฐ์ด๋ก ํํ๋๋ ๋ฏธ๋ก๊ฐ ์๋ค.
๋ฏธ๋ก์์ 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
์์ ์ ๋ ฅ 3
2 25
1011101110111011101110111
1110111011101110111011101
์์ ์ถ๋ ฅ 3
38
์์ ์ ๋ ฅ 4
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
์์ ์ถ๋ ฅ 4
13
๐ ์๋ฃ๊ตฌ์กฐ
์ด ๋ฌธ์ ๋ BFS๋ฅผ ์ฌ์ฉํด์ผ ํ๋ค. ์๋ํ๋ฉด โํน์ ๋ ธ๋์์ ํน์ ๋ ธ๋๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ & Weight ์์โ์ด๊ธฐ ๋๋ฌธ์ด๋ค.
BFS๋ก ๊ทธ๋ํ ์ ์ฒด๋ฅผ ํ์ํ๋ฉฐ (0,0) ์์น๋ก๋ถํฐ ์ด๋ ์นธ ์๋ฅผ ์ ๋ ฅํ๊ณ ์ต์ข ํ์์ด ์ข ๋ฃ๋์์ ๋ (N-1,M-1)์์น์ ์ด๋ ์นธ ์๋ฅผ ์ถ๋ ฅํ๋ค.
๋ฌธ์ ์์๋ ์์์ ์ด (1,1) ์ข ๋ฃ์ ์ด (N,M)์ด์ง๋ง ๋ฐฐ์ด์ index๊ฐ (0,0)๋ถํฐ ์์ํ๋ฏ๋ก ์ด๋ฅผ ๊ณ ๋ คํ์๋ค.
๐จ๐ปโ๐ป CODE
from collections import deque
N,M = map(int,input().split())
# ๋ฏธ๋ก ์ด๊ธฐํ
graph = [[0]*M for _ in range(N)]
# ๋ฏธ๋ก ์ ๋ณด ์
๋ ฅ
for i in range(N):
line = input()
for j in range(M):
graph[i][j] = int(line[j])
dx = [1,-1,0,0]
dy = [0,0,1,-1]
# BFS
def bfs(x,y):
q = deque([(x,y)])
while q:
cur = q.popleft()
ox,oy = cur[0],cur[1]
# ์ ๋ต์ ์ฐพ์ Case
if cur == (N-1,M-1):
break
# ์ ๋ต์ ์ฐพ์๊ฐ๋ ๊ณผ์
for i in range(4):
nx = cur[0]+dx[i]
ny = cur[1]+dy[i]
if 0<=nx<N and 0<=ny<M and graph[nx][ny] == 1:
q.append((nx,ny))
graph[nx][ny] = graph[ox][oy] + 1
bfs(0,0)
print(graph[N-1][M-1])