12886: 돌 그룹 && 16948: 데스 나이트

12886: 돌 그룹

• A + B + C의 값이 3의 배수가 아니라면 돌을 같은 개수로 만들 수 없으므로 print(0)을 해준다
• A + B + C의 값이 3의 배수라면 bfs 탐색을 시작한다
• • 여기서 포인트가 queue에 노드를 넣어줄 때, A, B, C 세 개 모두를 넣어주는 것이 아니라 두 개의 수만을 넣어줌 -> 나머지 하나의 수는 total - (A + B)로 구할 수 있음
• • [A, B], [B, C], [A, C]를 순회하면서, 선택된 두 개의 수 (이하 nextA, nextB)를 문제의 조건에 맞게 갱신해준 후, queue에 추가해줌
• • 중복되는 경우를 제거해주기 위해서 visit 리스트를 사용했는데, 이 때 visit 리스트를 2차원 리스트로 선언해줌

import sys
from collections import deque

def bfs():
    global A, B, C, total
    queue = deque()
    queue.append([A, B])
    visit[A][B] = True

    while queue:
        currA, currB = queue.popleft()
        currC = total - (currA + currB)
        if currA == currB == currC:
            print(1)
            return
        
        for nextA, nextB in [currA, currB], [currB, currC], [currA, currC]:
            if nextA > nextB:
                nextA -= nextB; nextB += nextB
            elif nextA < nextB:
                nextB -= nextA; nextA += nextA
            else:
                continue
            if not visit[nextA][nextB]:
                queue.append([nextA, nextB])
                visit[nextA][nextB] = True
    print(0) 


A, B, C = map(int, sys.stdin.readline()[:-1].split())
total = A + B + C
visit = [[False for _ in range(total + 1)] for _ in range(total + 1)]

if total % 3 != 0:
    print(0)
else:
    bfs()

16948: 데스 나이트

• 쉬운 bfs 문제

import sys
from collections import deque

def bfs():
    queue = deque([])
    queue.append([r1, c1])
    visit[r1][c1] += 1

    while queue:
        r, c = queue.popleft()
        if r == r2 and c == c2:
            print(visit[r][c])
            return
        
        for nr, nc in [r-2, c-1], [r-2, c+1], [r, c-2], [r, c+2], [r+2, c-1], [r+2, c+1]:
            if 0 <= nr < N and 0 <= nc < N:
                if visit[nr][nc] == -1:
                    queue.append([nr, nc])
                    visit[nr][nc] = visit[r][c] + 1
    print(-1)

N = int(input())
r1, c1, r2, c2 = map(int, sys.stdin.readline()[:-1].split())

visit = [[-1 for _ in range(N)] for _ in range(N)]
bfs()