์ง๋์์ ๋ชจ๋ ์ง์ ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฌธ์ .
์์ด๋์ด
BFS๋ฅผ ์ฌ์ฉํ๋ค. ์ง๋์์ ์ต๋จ๊ฑฐ๋ฆฌ == BFS ๊ฑฐ์ ๊ณต์์ฒ๋ผ ๋จธ๋ฆฌ์์ ๋์จ๋ค...
๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ๋ชฉํ ์ง์ (2๋ก ํ์)๊ณผ ๊ฐ ์ ์๋ ๋ (0์ผ๋ก ํ์)์ ์ขํ๋ ๋ฐ๋ก ์ ์ฅํด ๋๋ค.
์ ์ฒด ์ฝ๋
from collections import deque
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
start_x, start_y = 0, 0 # ๋ชฉํ ์ง์ (์์ ์ง์ )
maze = [] #์ง๋๋ฅผ ๋ด๋ ๋ฐฐ์ด
wall_list = [] # ๊ฐ ์ ์๋ ๋
๋ค์ ์ขํ๋ค
que = deque()
n, m = map(int, input().split())
visited = [[-1] * m for _ in range(n)]
for i in range(n):
line = [int(x) for x in input().split()]
for j in range(m):
if line[j] == 2:
start_x, start_y = i, j
elif line[j] == 0:
wall_list.append([i, j])
maze.append(line)
visited[start_x][start_y] = 0
for pos in wall_list:
visited[pos[0]][pos[1]] = 0
que.append([start_x, start_y])
while que:
x, y = que.popleft()
for i in range(4):
nx, ny = dx[i] + x, dy[i] + y
if 0 <= nx < n and 0 <= ny < m:
if maze[nx][ny] == 1 and visited[nx][ny] == -1:
visited[nx][ny] = visited[x][y] + 1
que.append([nx, ny])
for i in range(n):
print(" ".join(map(str, visited[i])))
์ฝ๋ ์ค๋ช
for i in range(n):
line = [int(x) for x in input().split()]
for j in range(m):
if line[j] == 2:
start_x, start_y = i, j
elif line[j] == 0:
wall_list.append([i, j])
maze.append(line)
์ง๋๋ฅผ ์ ๋ ฅ๋ฐ์๊ณผ ๋์์ ๋ชฉํ ์ง์ ๊ณผ ๊ฐ ์ ์๋ ๋ ๋ค์ ์ขํ๋ฅผ ์ ์ฅํด ์ค๋ค.
visited[start_x][start_y] = 0
for pos in wall_list:
visited[pos[0]][pos[1]] = 0
que.append([start_x, start_y])
while que:
x, y = que.popleft()
for i in range(4):
nx, ny = dx[i] + x, dy[i] + y
if 0 <= nx < n and 0 <= ny < m:
if maze[nx][ny] == 1 and visited[nx][ny] == -1:
visited[nx][ny] = visited[x][y] + 1
que.append([nx, ny])
BFS๋ฅผ ํ์ฉํด ๋ชจ๋ ์ง์ ์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํด์ค๋ค.
'๐งฉ Problem Solving > [๋ฐฑ์ค]' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 1697 ์จ๋ฐ๊ผญ์ง (python ํ์ด์ฌ) (0) | 2024.03.22 |
---|---|
[๋ฐฑ์ค] 15666 N๊ณผ M 12 (python ํ์ด์ฌ) (0) | 2024.03.21 |
[๋ฐฑ์ค] 1205 ๋ฑ์ ๊ตฌํ๊ธฐ (python ํ์ด์ฌ) (0) | 2024.03.19 |
[๋ฐฑ์ค] 21736 ํ๋ด๊ธฐ๋ ์น๊ตฌ๊ฐ ํ์ํด (python ํ์ด์ฌ) (0) | 2023.11.19 |
[๋ฐฑ์ค] 18110 solved.ac (+๋ฐ์ฌ๋ฆผ ํจ์ round์ ๋ํด) (python ํ์ด์ฌ) (0) | 2023.08.23 |