글 읽기 - 큐의 데이터타입을 int[]와 별도의 클래스로 하는 것이 메모리 차이가 나나요?

ckddn1224 3년 전 0

저는 BFS로 풀이했습니다.

처음에는 Queue<int[]> q = new LinkedList<>(); 이렇게 선언하여서, 큐에 삽입을 할때 q.offer(new int[]{x,y,k,cnt}); 이런식으로 했습니다.

위의 방법으로는 메모리초과가 나더군요.

아무리봐도 로직상 틀린게 없어보여 다른분들의 풀이를 참고하는데, 다른 것이 저부분을 별도의 클래스를 선언하여 사용하셨더라구요.

Queue<P> q = new LinkedList<>();한 후 삽입 시, q.offer(new P(x,y,k,cnt));이렇게요.

클래스 변수는 4개로 똑같았습니다. 그런데 이렇게 풀이한건 메모리초과가 안나더라구요.

혹시 두개의 차이가 뭔지 알 수 있을까요?

제생각으론 위에것도 int형 4개, 아래 클래스도 int형 4갠데 왜 메모리사용면에서 차이가나나요 ?

아래는 정답코드입니다. 아래 코드에서 38 라인입니다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ1600 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int[][] arr = new int[h][w];

        for (int i = 0; i < h; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < w; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ans = bfs(k, w, h, arr);

        bw.write(String.valueOf(ans));
        bw.close();
        br.close();

    }

    static int bfs(int k, int w, int h, int[][] arr) {
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        int[] hr = {-2, -2, -1, -1, 1, 1, 2, 2};
        int[] hc = {1, -1, 2, -2, 2, -2, 1, -1};

        boolean[][][] visited = new boolean[h][w][k + 1];
        Queue<Monkey> q = new LinkedList<>();
        q.offer(new Monkey(0, 0, 0, 0));
        visited[0][0][0] = true;
        int res = -1;

        while (!q.isEmpty()) {
            Monkey cur = q.poll();
            if (cur.r == h - 1 && cur.c == w - 1) {
                return cur.cnt;
            }

            // 상하좌우 이동
            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                if (isPossible(nr, nc, h, w) && arr[nr][nc] == 0 && !visited[nr][nc][cur.k]) {
                    q.offer(new Monkey(nr, nc, cur.k, cur.cnt + 1));
                    visited[nr][nc][cur.k] = true;
                }
            }

            // 말 이동을 k번 했으면 더이상 말 이동은 불가능
            if (cur.k == k) {
                continue;
            }

            // 말 이동
            for (int i = 0; i < 8; i++) {
                int nr = cur.r + hr[i];
                int nc = cur.c + hc[i];
                if (isPossible(nr, nc, h, w) && arr[nr][nc] == 0 && !visited[nr][nc][cur.k + 1]) {
                    q.offer(new Monkey(nr, nc, cur.k + 1, cur.cnt + 1));
                    visited[nr][nc][cur.k + 1] = true;
                }
            }
        }
        return res;
    }

    static boolean isPossible(int x, int y, int h, int w) {
        if (x >= 0 && x < h && y >= 0 && y < w) {
            return true;
        } else {
            return false;
        }
    }

    static class Monkey {
        int r, c, k, cnt;

        Monkey(int r, int c, int k, int cnt) {
            this.r = r;
            this.c = c;
            this.k = k;
            this.cnt = cnt;
        }
    }

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

큐의 데이터타입을 int[]와 별도의 클래스로 하는 것이 메모리 차이가 나나요?

ckddn1224 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말