[백준] 7562, 1697

나이트의 이동 (7562번)

• 사이트/난이도: 백준 / 실버1
• 코드

#실버1 나이트의 이동
import sys
from collections import deque
input = sys.stdin.readline

# 8방향
dx = [1, 1, 2, 2, -1, -1, -2, -2]
dy = [-2, 2, -1, 1, -2, 2, -1, 1]

def bfs(x, y, target_x, target_y):
    q = deque([])
    q.append((x,y))
    graph[x][y] = 1
    while q:
        x, y = q.popleft()
        if x == target_x and y == target_y:
            return graph[x][y] - 1

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] != 0:
                continue
            q.append((nx, ny))
            graph[nx][ny] = graph[x][y] + 1

t = int(input())
for _ in range(t):
    n = int(input())
    x, y = map(int, input().split())
    target_x, target_y = map(int, input().split())
    graph = [[0] * n for _ in range(n)]

    print(bfs(x, y, target_x, target_y))

• 느낀점
  • 나이트의 이동 방향 8개 적어놓고 bfs 이용해서 풀이
  • 이동횟수는 해당 체스판을 0으로 다 초기화하고 갈때마다 +1 씩 해주기

숨바꼭질 (1697번)

• 사이트/난이도: 백준 / 실버1
• 코드

# 실버1 숨바꼭질
import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
visited = [False] * (100001)

def bfs(n, k):
    q = deque([])
    q.append((n, 0))
    dx = [1, -1]

    while q:
        loc, time = q.popleft()
        if loc == k:
            return time
        visited[loc] = True
        
        # 걸을 때
        for i in range(2):
            nx = loc + dx[i]
            if nx < 0 or nx > 100000:
                continue
            if visited[nx]:
                continue
            q.append((nx, time+1))
        
        # 순간이동 할 때
        nx = loc * 2
        if nx >= 0 and nx <= 100000:
            q.append((nx, time+1))

print(bfs(n, k))

# 다른사람 풀이
def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if v == k:
            return array[v]
        for next_v in (v-1, v+1, 2*v):
            if 0 <= next_v < MAX and not array[next_v]:
                array[next_v] = array[v] + 1
                q.append(next_v)

MAX = 100001
n, k = map(int, sys.stdin.readline().split())
array = [0] * MAX
print(bfs(n))

• 느낀점
  • 최단 거리를 찾는 문제므로 dfs보다는 bfs를 선택하면 더 효율적이다.
  • 움직이는 방법이 +1, -1, *2 3가지므로 해당 방법을 통해 조건에 맞으면 이동하면서 답을 구한다.
  • 다른사람 풀이를 보니 3가지 방법으로 이동할 때 for in 을 이용해서 더 간결하다.
  • 그리고 난 중복을 제거하기 위해 visited랑 횟수기록을 위해 time 이란 변수를 큐에 넣었는데 그냥 전체 맵을 0으로 기록하고 움직일때마다 +1 하면 한번에 해결할 수 있다.