글 읽기 - C++ 메모리 초과 ... 제코드 어디가문제일까요

dobidugi 2년 전 0

안녕하세요 14번실패끝에 제코드가 진짜 어디가 문제인지 몰라서 질문드립니다.

코드 이해하기 쉽게 주석을 달아놨습니다...

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
struct obj {
	int y, x;
	bool is_crash;
};

int bfs(vector<vector<char>>& board, int y, int x)
{
	vector<vector<pair<int, bool>>> visit(y, vector<pair<int, bool>>(x, {-1, false}));
	queue<obj> q;
	q.push({ 0, 0, false });
	visit[0][0] = { 1, false };
	while (!q.empty())
	{
		obj cur = q.front(); q.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int ny = cur.y + dy[dir];
			int nx = cur.x + dx[dir];
			if (ny == y - 1 && nx == x - 1)
			{
				return visit[cur.y][cur.x].first + 1;
			}
			if (ny < 0 || ny >= y || nx < 0 || nx >= x) continue; // 범위 넘어갈시 넘어감
			if (visit[ny][nx].first != -1)
			{
				if (visit[ny][nx].second == cur.is_crash) continue;
			}
			if (board[ny][nx] == '0') // 뚫려있을때
			{
				q.push({ ny, nx, cur.is_crash }); // 현재 벽부심상태를넣음 
				visit[ny][nx].first = visit[cur.y][cur.x].first + 1;
				visit[ny][nx].second = cur.is_crash;
			}
			if (board[ny][nx] == '1' && !cur.is_crash) // 벽으로 막혀있고 한번도안부셨을때
			{
				q.push({ ny, nx, true }); // 부셨음을 의미하고 큐에넣어줌
				visit[ny][nx].first = visit[cur.y][cur.x].first + 1;
				visit[ny][nx].second = true;
			}
		}
	}
	return -1;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int y, x;
	cin >> y >> x;

	vector<vector<char>> board(y, vector<char>(x, '0'));
	for (int i = 0; i < y; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < x; j++)
		{
			board[i][j] = s[j];
		}
	}

	cout << bfs(board, y, x);
	return 0;
}

pichulia 2년 전 3

visit 처리가 제대로 안되고 있습니다.

해당 데이터에서 0, 0 에 몇번 접근하는지 확인해보세요

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

문제

문제

출처

ICPC

C++ 메모리 초과 ... 제코드 어디가문제일까요

dobidugi 2년 전 0

pichulia 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말