문제 출처: https://www.acmicpc.net/problem/16948
[내가 맨 처음에 제출한 문제 답]
n = int(sys.stdin.readline())
r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
c = [[0] * n for _ in range(n)]
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]
dq = deque()
dq.append((r1, c1))
while dq:
x, y = dq.popleft()
if x == r2 and y == c2: break
else:
for k in range(6):
a, b = x + dx[k], y + dy[k]
if 0 <= a < n and 0 <= b < n:
if c[a][b] == 0 or c[x][y] + 1 < c[a][b]:
c[a][b] = c[x][y] + 1
dq.append((a, b))
if c[r2][c2] == 0: print(-1)
else: print(c[r2][c2])이렇게 했더니 124ms가 나왔다 더 빠르게 해결한 코드가 있길래 그걸 보고 수정함.
[수정한 이후 코드]
n = int(sys.stdin.readline())
r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
c = [[-1] * n for _ in range(n)]
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]
dq = deque()
dq.append((r1, c1))
c[r1][c1] = 0
while dq:
x, y = dq.popleft()
if x == r2 and y == c2: break
for k in range(6):
a, b = x + dx[k], y + dy[k]
if 0 <= a < n and 0 <= b < n and c[a][b] == -1:
dq.append((a, b))
c[a][b] = c[x][y] + 1
print(c[r2][c2])
거의 비슷하긴 한데... 바뀐 부분 있긴함
1. c를 애초에 -1로 초기화하고 시작지점은 0으로 따로 설정
2. c배열에서 -1(초기값)이 아닌 다른 값으로 채워져 있는 애들은 시작점으로부터 자기 자신까지의 최소이동횟수를 이미 가지고 있는 것임.
BFS : deque를 이용하는 FIFO(First In First Out)방식, 임의의 노드에서 인접한 자식 노드들을 다 탐색한 뒤에 한 단계 깊이 내려가 같은 방법으로 탐색함(너비우선탐색)
DFS : 임의의 노드로부터 연결된 제일 깊은 곳의 자식 노드까지 탐색한 뒤에(갈수 있는 제일 깊은 노드까지 갔다가) 바로 직전 갈림길로 돌아와서 또 다시 제일 깊은 곳까지 탐색하는 방법이다.(깊이우선탐색)
bfs의 인접한 자식 노드들을 가장 먼저 탐색하는 특성 때문에 c배열의 특정 칸이 초기값이 아닐 경우 -> 최소이동횟수값을 가지게 됨
100% + 100%