글 읽기 - 이 문제를 3차원 배열을 쓰지 않고 해결 할 수는 없나요?

shinbian11 3년 전 0

3차원 배열로 해결하는 방법 말고, 2차원 배열로 따로따로 구현해서 저렇게 비슷하게 할 수는 없나요?

물론 2차원 배열 2개로, 하나는 벽을 부신 횟수가 0일떄, 벽을 부신 횟수가 1일때의 배열을 따로 따로 구현해야 하는 방법은 알지만, 그렇게 할바에는 그냥 3차원 배열 선언해서 하면 되는 것이기 때문에, 굳이 그렇게는 하지 않았고요.

제가 궁금한건, 60,67번째 줄처럼 선언을 해서는 절대 풀 수 없는지가 궁금합니다.

이렇게 제출했더니 일단 테스트 케이스는 맞지만, 테스트 케이스만 통과하고 실제 돌려보면 11%정도에서 틀렸다고 뜨는데, 틀린 이유가 궁금합니다.

#include <bits/stdc++.h>

// F_I 사용하면 cin 과 scanf 를 섞어서 쓰면 안된다!
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;

ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수

int a[1001][1001]; // 배열 저장
int wall[1001][1001]; // wall[x][y] = x행 y열인 상황에서 벽을 부시지 않았으면 0 , 이미 벽을 한번 부신 상태면 1 저장
//bool visit[1001][1001]; //방문처리 기록
int cnt[1001][1001]; // 실제 최단거리 횟수 기록

int dir[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };
int n, m;

int isinside(int x, int y)
{
	if (x >= 0 && x < n && y >= 0 && y < m)
		return 1;
	else
		return 0;
}

int main()
{
	//F_I;

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &a[i][j]);
		}
	}

	queue<pl> q;
	q.push(make_pair(0, 0));
	cnt[0][0] = 1;

	while (!q.empty())
	{

		int x = q.front().first;
		int y = q.front().second;
		//visit[x][y] = true;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			if (isinside(nx, ny) && cnt[nx][ny] ==0 && a[nx][ny] == 1 && wall[x][y] == 0) //다음 갈 곳이 벽인데, 아직 한번도 벽을 부시지 않은 경우. 
			{
				//visit[nx][ny] = true;
				cnt[nx][ny] = cnt[x][y] + 1; //횟수 + 1 
				wall[nx][ny] = wall[x][y] + 1; // 벽을 한번 부시게 됨
				q.push(make_pair(nx, ny));
			}
			if (isinside(nx, ny) && cnt[nx][ny] == 0 && a[nx][ny] == 0) //다음 갈 곳이 벽이 아니고 그냥 갈수 있는 곳일떄
			{
				//visit[nx][ny] = true;
				cnt[nx][ny] = cnt[x][y] + 1;
				wall[nx][ny] = wall[x][y];
				q.push(make_pair(nx, ny));
			}
		}
	}
	if (cnt[n - 1][m - 1] != 0)
		cout << cnt[n - 1][m - 1] << '\n';
	else
		cout << -1 << '\n';
	return 0;
}

shinbian11 3년 전 0

감사합니다

pichulia 3년 전 0

반례입니다.

열심히 노력하면 (벽을 딱 1개만 부수는 이 문제에 한해서) 3차원배열을 안쓰고 풀 수 있는 방법이 있습니다.

luniro 3년 전 0

벽을 10개까지 부수는 벽 부수고 이동하기2까지도 2개의 2차원배열로 풀 수 있기는 합니다

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

문제

문제

출처

ICPC

이 문제를 3차원 배열을 쓰지 않고 해결 할 수는 없나요?

shinbian11 3년 전 0

shinbian11 3년 전 0

pichulia 3년 전 0

luniro 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말