DFS/BFS 완전정복기4 -상하좌우로 움직이지 않는 경우-

1. 문제1

 

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

나이트가 최소 몇번 이동하면 주어진 칸으로 이동할 수 있는지 구하는 문제

 

어렵게 생각할 필요 전혀 없이, 문제에서 주어지는 1번에 이동할 수 있는 경우를 모두 델타배열에 저장하여, 그것을 순회하면 된다

 

 

2. 풀이

 

어렵게 생각할 필요 전혀 없고 일반적인 bfs 흐름으로 가다가 

 

상하좌우 델타배열 [[0,1],[1,0],[0,-1],[-1,0]]을 나이트가 이동할 수 있는 칸으로 바꾼 델타배열 

 

delta = [(2,1),(2,-1),(1,2),(1,-2),(-1,2),(-1,-2),(-2,1),(-2,-1)]로 바꾸기만 하면 된다

 

from collections import deque
from sys import stdin

def bfs(x,y,s,g,n,maps):
    
    queue = deque([(x,y)])

    if x == s and y == g:
        
        return maps[y][x]
    
    else:
        
        maps[y][x] = 1

        delta = [(2,1),(2,-1),(1,2),(1,-2),(-1,2),(-1,-2),(-2,1),(-2,-1)]

        while queue:
            
            x,y = queue.popleft()

            for ni,nj in delta:
                
                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= n-1 and maps[dy][dx] == 0:
                    
                    queue.append((dx,dy))
                    maps[dy][dx] = maps[y][x] + 1

                    if dx == s and dy == g:
                        
                        return maps[dy][dx]-1
        

    
T = int(input())

for _ in range(1,T+1):
    
    n = int(stdin.readline())

    maps = [[0]*n for _ in range(n)]

    x,y = map(int,stdin.readline().split())

    a,b = map(int,stdin.readline().split())

    print(bfs(x,y,a,b,n,maps))

 

3. 문제2

 

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

일직선상에 시작점 n과 도착점 k가 주어질때 n에서 k로 최소 몇번만에 갈 수 있는지 구하는 문제

 

이번에 n에서 1초 후에 n-1, n+1, 2n으로 갈 수 있다고 나와있는데

 

역시 어렵게 생각할 필요가 전혀 없이 3가지 경우를 델타배열에 저장하여 그것을 순회하기만 하면 된다

 

 

4. 풀이

 

어렵게 생각할 필요 전혀 없고 시작점 n에서 1번에 이동할 수 있는 경우는 n-1,n+1,2n이므로 이것을 델타배열 [-1,1,n]으로 만들어서 순회하면 된다

 

이게 제일 핵심이고 나머지는 사실 디테일한 부분

 

제약조건을 보면 처음부터 n과 k가 같은경우가 있을 수 있음

 

그래서 n == k이면 바로 0을 print

 

그리고 visited를 [0]*100001로 초기화하는 이유는 규칙에 따라 움직이다가

 

n이 증가하면서 k로 가는데, k보다 커져가지고 

 

k보다 큰 상태에서 작아지면서 k로 접근할 수 있어서 그렇다

 

 

위와 같은 경우 크기를 15로 설정해버리면 오답을 낼 수 있음

 

from collections import deque
from sys import stdin

def bfs(n,k):
    
    visited = [0] * 100001

    queue = deque([n])
    
    visited[n] = 1

    while queue:
        
        n = queue.popleft()

        for j in [-1,1,n]:
            
            dn = n + j

            if dn >= 0 and dn <= 100000 and visited[dn] == 0:
                
                queue.append(dn)
                visited[dn] = visited[n] + 1

                if dn == k:
                    
                    return visited[dn] - 1
                
n,k = map(int,stdin.readline().split())

if n == k:
    
    print(0)

else:

    print(bfs(n,k))