SWEA 5247 - 연산 [Java][Python]

문제

SW Expert Academy

풀이1

Java로 열심히 풀었지만 이 문제는 Python만 제출이 가능했다😅

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			System.out.println("#" + t + " " + solution(N, M));
		}
		
		sc.close();
	}
	
	static final int MAX = 1_000_000;
	
	private static int solution(int N, int M) {
		Queue<Integer[]> queue = new LinkedList<>();
		boolean[][] visited = new boolean[MAX+1][4];
		queue.add(new Integer[] {N, 0});
		
		while(!queue.isEmpty()) {
			Integer[] cur = queue.poll();
			int x = cur[0], c = cur[1];
			if (x == M) {
				return c;
			}
			
			int[] dx = {x, 1, -1, -10};
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				if (1 <= nx && nx <= MAX && !visited[nx][i]) {
					visited[nx][i] = true;
					queue.add(new Integer[] {nx, c+1});
				}
			}
		}
		
		return -1;
	}
}

풀이2

Python으로 다시 코드를 작성했다. 테스트 케이스들은 모두 통과했지만 채점에서 Runtime Error가 발생했다.

from collections import deque

MAX = 10 ** 6

def solution(N, M):
    dq = deque()
    visited = list([False] * 4 for _ in range(MAX+1))
    dq.append((N, 0))

    while len(dq) > 0:
        x, c = dq.popleft()
        if x == M:
            return c

        dx = [x, 1, -1, -10]
        for i in range(4):
            nx = x + dx[i]
            if 1 <= nx <= MAX and not visited[nx][i]:
                visited[nx][i] = True
                dq.append((nx, c+1))

    return -1

T = int(input())
for t in range(1, T+1):
    N, M = map(int, input().split())
    print(f"#{t} {solution(N, M)}")

풀이3

BFS는 가장 먼저 특정 노드에 도달했을 때가 무조건 최단 거리임을 보장하기 때문에 visited 배열이 굳이 4차원일 필요는 없었다. 1차원으로 수정하고 다시 제출했더니 이번에는 통과했다.

from collections import deque

MAX = 10 ** 6

def solution(n, m):
    dq = deque()
    visited = [False] * (MAX+1)
    dq.append((n, 0))

    while len(dq) > 0:
        x, c = dq.popleft()
        if x == m:
            return c

        dx = [x, 1, -1, -10]
        for i in range(4):
            nx = x + dx[i]
            if 1 <= nx <= MAX and not visited[nx]:
                visited[nx] = True
                dq.append((nx, c+1))

    return -1

T = int(input())
for t in range(1, T+1):
    N, M = map(int, input().split())
    print(f"#{t} {solution(N, M)}")

 

풀이2에서 Runtime Error가 발생했던 이유는 아무래도 OOM 때문이었던 것 같다.