Baekjoon - 1928

문제

Solved.ac Class3++

1차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int radderSize = Integer.parseInt(split[0]);
		int snakeSize = Integer.parseInt(split[1]);
		int[] board = new int[100 + 1];
		boolean[] isVisit = new boolean[100 + 1];
		int answer = 0;

		for (int i = 0; i < radderSize; i++) {
			String[] data = br.readLine().split(" ");
			board[Integer.parseInt(data[0])] = Integer.parseInt(data[1]);
		}

		for (int i = 0; i < snakeSize; i++) {
			String[] data = br.readLine().split(" ");
			board[Integer.parseInt(data[0])] = Integer.parseInt(data[1]);
		}

		Queue<VisitData> data = new LinkedList<>();
		isVisit[1] = true;
		for (int i = 2; i <= 7; i++) { // 1부터 시작
			data.add(new VisitData(1, i));
			isVisit[i] = true;
		}

		while (!data.isEmpty()) {
			VisitData visit = data.remove();
			int countNow = visit.count;
			int visitNow = visit.visit;

			if (visitNow == 100) {
				answer = countNow;
				break;
			}

			if (board[visitNow] != 0) {
				visitNow = board[visitNow];
			}

			for (int i = 1; i <= 6; i++) {
				if (visitNow + i > 100) {
					continue;
				}
				data.add(new VisitData(countNow + 1, visitNow + i));
				isVisit[visitNow + i] = true;
			}
		}

		System.out.println(answer);
	}

	static class VisitData {
		public VisitData(int count, int visit) {
			this.count = count;
			this.visit = visit;
		}

		private final int count;
		private final int visit;
	}

}

메모리 초과

2~4차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int radderSize = Integer.parseInt(split[0]);
		int snakeSize = Integer.parseInt(split[1]);
		int[] board = new int[100 + 1]; // 방문 count
		boolean[] isVisit = new boolean[100 + 1]; // 방문 여부
		int[] moveInfo = new int[100 + 1]; // snake, ladder

		for (int i = 0; i < radderSize; i++) {
			String[] data = br.readLine().split(" ");
			moveInfo[Integer.parseInt(data[0])] = Integer.parseInt(data[1]);
		}

		for (int i = 0; i < snakeSize; i++) {
			String[] data = br.readLine().split(" ");
			moveInfo[Integer.parseInt(data[0])] = Integer.parseInt(data[1]);
		}

		Queue<Integer> queue = new LinkedList<>();
		isVisit[1] = true;
		board[1] = 0;
		queue.add(1);

		while (!queue.isEmpty()) {
			int now = queue.remove();
			if (now == 100) {
				break;
			}
			isVisit[now] = true;

			if (moveInfo[now] != 0) {
				int before = now;
				now = moveInfo[now];
				isVisit[now] = true;
				board[now] = board[before];
			}

			for (int i = 1; i <= 6; i++) {
				if (now + i > 100 || isVisit[now + i]) {
					continue;
				}
				queue.add(now + i);
				isVisit[now + i] = true;
				board[now + i] = board[now] + 1;
			}
		}
		System.out.println(board[100]);
	}
}

코드를 일부 수정해도 계속 메모리 초과가 났고 queue에 들어가는 데이터가 많아지는것을 문제로 파악해서 코드를 수정했다.

성공

ToKotlin

fun main() {
    val split = readln().split(" ")
    val radderSize = split[0].toInt()
    val snakeSize = split[1].toInt()
    val board = IntArray(100 + 1)
    val isVisit = BooleanArray(100 + 1)
    val moveInfo = IntArray(100 + 1)


    for (i in 0..<radderSize) {
        val data = readln().split(" ")
        moveInfo[data[0].toInt()] = data[1].toInt()
    }

    for (i in 0..<snakeSize) {
        val data = readln().split(" ")
        moveInfo[data[0].toInt()] = data[1].toInt()
    }

    val queue: Queue<Int> = LinkedList()
    isVisit[1] = true
    board[1] = 0
    queue.add(1)

    while (queue.isNotEmpty()) {
        var now = queue.remove()
        if (now == 100) {
            break
        }
        isVisit[now] = true

        if (moveInfo[now] != 0) {
            val before = now
            now = moveInfo[now];
            isVisit[now] = true;
            board[now] = board[before];
        }

        for (i in 1..6) {
            if (now + i > 100 || isVisit[now + i]) {
                continue;
            }
            queue.add(now + i);
            isVisit[now + i] = true;
            board[now + i] = board[now] + 1;
        }
    }
    print(board[100])
}