[SWEA/D3] 16800 구구단 걷기

문제 바로가기

SW Expert Academy

나의 코드 및 설명 - BFS로 풀려다가 런타임에러 발생

from collections import deque

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    v[y][x] = 1
    while queue:
        x,y = queue.popleft()
        if x*y == n:
            return v[y][x] - 1
        for i in range(2):
            nx = x+dx[i]
            ny = y + dy[i]
            queue.append((nx,ny))
            v[ny][nx] = v[y][x] + 1

t = int(input())
for test_case in range(1,t+1):
    n = int(input())
    v = [[0] * n for _ in range(n)]
    dx= [1,0]
    dy = [0,1]
    print(bfs(1,1))

다른 코드 및 설명 01 - 임의의 최솟값 비교 변수(ans) 활용하여 최솟값을 구하는 방식

import math
t = int(input())
for test_case in range(1,t+1):
    n = int(input())
    total = []
    #n의 제곱근만큼만 확인해보면 된다.
    for i in range(1, int(math.sqrt(n)) +1):
        if n%i == 0:
            total.append((i, n//i)) #서로 곱했을 때 n이 나오는 두 숫자를 리스트에 저장한다.
    ans = 1000000e9
    for (x,y) in total: #리스트에 저장된 숫자들을 하나씩 꺼내본다.
        distance = x-1 + y-1 #(1,1)부터 (x,y)까지의 거리를 distance에 저장
        if ans > distance: #최솟값을 찾는다.
            ans = distance
    print("#{} {}".format(test_case, ans))

다른 코드 및 설명 02 - 좌표가 저장되어 있던 리스트에 거리정보를 저장하고, min() 메서드를 통해 최솟값을 구하는 방식

import math
t = int(input())
for test_case in range(1,t+1):
    n = int(input())
    total = []
    for i in range(1, int(math.sqrt(n)) +1):
        if n%i == 0:
            total.append((i, n//i))
    for i in range(len(total)): #1,1에서 시작
        distance = total[i][0]-1 + total[i][1]-1
        total[i] = distance
    print("#{} {}".format(test_case, min(total)))

피드백

n이 x,y좌표의 곱이기 때문에 x,y 좌표만 구한다면 최소 거리를 구할 수 있다. 최단거리를 구하는 문제이기 때문에 기계적으로 BFS을 활용하여 문제를 해결하려 했는데, 3번 TC의 어마무시한 입력 값 때문에 실패했다. 고민하다가 다른 사람의 코드를 보고 방향을 잡을 수 있었다. 생각보다 복잡하지 않고 단순하게 풀 수 있었다. 약간의 꼼수도 필요한 문제. 문제를 풀 때 이러한 발상의 창의성을 기르기 위해 노력해야겠다.