글 읽기 - 메모리 초과 관련된 부분입니다.

sso07012 2년 전 0

제가 작성했던 코드는 아래와 같습니다. 말의 움직임 Count변수인 k의 횟수에 따른 방문 횟수 구분을 위한 visited 3차원 배열을 이용해서 구현했습니다. 그러나 메모리 초과가 났었고, 질문 게시판을 찾아보니 저와 비슷한 코드인데 AC가 되신 분의 코드를 발견했습니다. 어떤 차이점이 있는지 알려주시면 감사하겠습니다.

비슷하신 분의 코드 : https://www.acmicpc.net/board/...

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int k, w, h;
int visited[200][200][31];
int graph[200][200];
void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(graph, 0, sizeof(graph));
    fill(&visited[0][0][0], &visited[0][0][0] + sizeof(visited) / sizeof(int), 987654321);

    cin >> k;
    cin >> w >> h;
    for(int i = 0; i < w; i++) {
        for(int j = 0; j < h; j++) {
            cin >> graph[i][j];
        }
    }

    solve();

    return 0;
}

void solve() {
    struct node {
        int x; // x좌표
        int y; // y좌표
        int cnt; // 남은 말 이동 횟수
    };
    queue<node> q;
    int dx[] = {1, -1, 0, 0};
    int dxHorse[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {0, 0, 1, -1};
    int dyHorse[] = {-1, -2, -2, -1, 1, 2, 2, 1};

    q.push({0, 0, k});   
    visited[0][0][k] = 0;
    while(!q.empty()) {
        node now = q.front();
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(0 > nx || nx >= w || 0 > ny || ny >= h) {
                continue;
            }

            if(graph[nx][ny] != 1) {
                if(visited[nx][ny][now.cnt] > visited[now.x][now.y][now.cnt] + 1) {
                    visited[nx][ny][now.cnt] = visited[now.x][now.y][now.cnt] + 1;

                    q.push({nx, ny, now. cnt});
                }
            }
        }

        // 말의 방식으로 이동했을 때
        if(now.cnt > 0) {
            for(int i = 0; i < 8; i++) {
                int nx = now.x + dxHorse[i];
                int ny = now.y + dyHorse[i];

                if(0 > nx || nx >= w || 0 > ny || ny >= h) {
                    continue;
                }

                if(graph[nx][ny] != 1) {
                    if(visited[nx][ny][now.cnt] > visited[now.x][now.y][now.cnt] + 1) {
                        visited[nx][ny][now.cnt - 1] = visited[now.x][now.y][now.cnt] + 1;
                        q.push({nx, ny, now.cnt - 1});
                    }
                }
            }
        }  
    }

    // 결과 출력
    int result = 987654321;
    for(int i = 0; i < k + 1; i++) {
        result = min(result, visited[w -  1][h - 1][i]);
    }

    if(result == 987654321) {
        cout << -1 << endl;
    }
    else {
        cout << result << endl;
    }
}

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

문제

문제

출처

ICPC

메모리 초과 관련된 부분입니다.

sso07012 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말