[백준]230310-12 문제풀이

9019. DSLR

from collections import deque
import sys
input = sys.stdin.readline

def zero(n):
    while len(str(n)) < 4:
        n = '0' + str(n)
    return str(n)

def D(n):
    return (n * 2) % 10000

def S(n):
    if n > 0:
        return n - 1
    else:
        return 9999

def L(n):
    return int(n[1:] + n[0])

def R(n):
    return int(n[-1] + n[:-1])

T = int(input())
for tc in range(T):
    a, b = map(int, input().split())
    queue = deque([])
    queue.append(a)
    visited = [''] * 10000
    while queue:
        now = queue.popleft()
        if now == b:
            ans = visited[now]
            break
        if now != 0 and not visited[D(now)]:
            queue.append(D(now))
            visited[D(now)] = visited[now] + 'D'
        if not visited[S(now)]:
            queue.append(S(now))
            visited[S(now)] = visited[now] + 'S'
        if not visited[(L(zero(now)))]:
            queue.append(L(zero(now)))
            visited[L(zero(now))] = visited[now] + 'L'
        if not visited[(R(zero(now)))]:
            queue.append(R(zero(now)))
            visited[R(zero(now))] = visited[now] + 'R'
    print(ans)

확실히 BFS는 손에 익으니까 할만한 것 같다. 원래 큐에 방문한 문자열을 전부 저장해가면서 했는데 메모리 초과가 떠서 각 숫자를 인덱스로 하는 방문 목록에 문자 하나씩 추가해가면서 답을 찾아냈다. R이랑 L 구현 과정, 큐에 append하는 과정이 조금 지저분하긴 해서 아쉽다.

9663. N-Queen

import sys
input = sys.stdin.readline

N = int(input())

def ispromising(n):
    for i in range(n):
        if board[n] == board[i] or abs(board[n] - board[i]) == abs(n - i):
            return False
    return True

def queen(n):
    global ans
    if n == N:
        ans += 1
        return
    for i in range(N):
        board[n] = i
        if ispromising(n):
            queen(n + 1)

board = [0] * N
ans = 0
queen(0)
print(ans)

엄청 유명한 백트래킹 문제. 8방향 델타, 쌩dfs 쓰면서 정통(이라고 생각했던) 방식으로 풀었는데 답도 안나오고 애초에 문제에서 메모리를 빡빡하게 줘서 정해진 답으로 풀어야 한다고 한다. 그래서 구글링 했는데 답 안보고 풀면 절대 못풀었을듯한... ispromising을 쓰면서 유망한지를 확인하는 과정, 퀸을 놓을 열(행)을 결정하는 과정, 대각선 여부를 확인하는 과정 모두 깔끔하게 된 정답 코드를 보면서 아직 공부해야 할게 너무 많이 남았다고 느꼈다. 아직도 사고방식이 브루트포스랑 구현에서 벗어나질 못하고 있는데, 이게 처음에 와꾸 짤 때 방해가 되는 것 같아서 어떻게 해야할지 고민이다.