https://www.acmicpc.net/problem/7562
๋ฏธ๋ก ์ฐพ๊ธฐ๋ ๋น์ทํ๋ค.
์ ๋ฒ์ ํ์ ๋ฌธ์ ํ ๋ bfs๋ก ์๊ฐ ์ด๊ณผ๊ฐ ๋ฌ ๊ฒฝํ์ ์ผ์ dfs๋ก ํ์๋๋ฐ ํด๊ฒฐ์ด ์ ๋๋ค.
์๊ฐํด๋ณด๋ค๊ฐ bfs๋ก ํ์๋๋ฐ ๋ฐ๋ก ๋ต์ด ๋์๋ค.
๋ด ์๊ฐ์๋ bfs๋๊น ์์ฐ์ค๋ฝ๊ฒ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ๋์ค๋๊น(depth ๋ณ๋ก ํ์) ์ด๋ฐ ๋ฌธ์ ๋ bfs๋ก ํธ๋ ๊ฒ ์ข์ ๊ฑฐ ๊ฐ๋ค.
ํ์ด ๊ณผ์
dx = [2,2,1,1,-1,-1,-2,-2]
dy = [1,-1,2,-2,2,-2,1,-1]
์ด๋ฐ ์์ผ๋ก ๋์ดํธ๊ฐ ์ด๋ํ๋ ์ขํ๋ฅผ ๋ง๋ค์ด๋๋ฉด ๋งค์ฐ ํธํจ.
๋๋จธ์ง๋ bfs๋ฅผ ์๊ณ ์์ผ๋ฉด ์ฝ๊ฒ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
์ ์ฒด ์ฝ๋
from collections import deque
import sys
sys.setrecursionlimit(10**6)
dx = [2,2,1,1,-1,-1,-2,-2]
dy = [1,-1,2,-2,2,-2,1,-1]
T = int(input())
def bfs():
deq = deque()
deq.append([now_x,now_y])
chesspan[now_x][now_y] = 1
while deq:
x,y = deq.popleft()
for i in range(8):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < L and 0 <= ny < L:
if chesspan[nx][ny] == 0:
chesspan[nx][ny] = chesspan[x][y] + 1
deq.append([nx,ny])
for _ in range(T):
L = int(input())
chesspan = [[0 for _ in range(L)] for _ in range(L)]
now_x, now_y = map(int,input().split())
move_x, move_y = map(int,input().split())
bfs()
print(chesspan[move_x][move_y] - 1)
๋ฐฉ๋ฌธ ํ์ธ์ ๋ฐ๋ก ๋ฐฉ๋ฌธ์ ํ์ธํ๋ ๋ฆฌ์คํธ ์์ด ํ์๋ฅผ ์ ์ฅํ๋ ๋ฆฌ์คํธ๋ก ํด๊ฒฐํ๋ค.
๋งจ ์ฒ์ ์์ํ๋ ์์น๋ฅผ 1๋ก ํ๋ฉด ๋จ.
๋์ ์ด๋ ๊ฒ ๋๋ฉด ๋ชจ๋ ์ด๋ ํ์์ +1์ด ๋๋๊น ์ ๋ต์ ์ถ๋ ฅํ ๋ -1์ ํด์ค๋ค.
'๐งฉ Problem Solving > [๋ฐฑ์ค]' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 16234 ์ธ๊ตฌ์ด๋ (python ํ์ด์ฌ) (0) | 2022.06.21 |
---|---|
[๋ฐฑ์ค] 1389 ์ผ๋น ๋ฒ ์ด์ปจ์ 6๋จ๊ณ ๋ฒ์น (python ํ์ด์ฌ) (0) | 2022.06.19 |
[๋ฐฑ์ค] 11404 ํ๋ก์ด๋ (python ํ์ด์ฌ) (0) | 2022.06.18 |
[๋ฐฑ์ค] 17070 ํ์ดํ ์ฎ๊ธฐ๊ธฐ 1 (python ํ์ด์ฌ) (0) | 2022.06.16 |
[๋ฐฑ์ค] 10026 ์ ๋ก์์ฝ(python ํ์ด์ฌ) (0) | 2022.06.15 |