글 읽기 - 벽 부수고 이동하기 틀린부분/반례좀 찾아주실 수 있을까요?

stronghsg 4년 전 0

아래와 같이 짰는데요..

혹시 틀린 부분을 지적받을 수 있을까요?

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int check[1000][1000][2]; // [0]: 방문여부, [1]: 벽부숨 여부
int nodes[1000][1000];

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void bfs(int x, int y, int W, int H)
{
	queue <tuple<int, int, int>> q; // x, y, 벽부숨
	int visit = 1;
	check[y][x][0] = visit; // 방문
	int wall = 0;
	check[y][x][1] = wall; // 벽 안부숨
	q.push(make_tuple(0, 0, wall));
	while (!q.empty())
	{
		int cur_x, cur_y, cur_w;
		tie(cur_x, cur_y, cur_w) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + dx[i];
			int next_y = cur_y + dy[i];
			if (0 <= next_x && next_x < W && 0 <= next_y && next_y < H)
			{ // 범위 안이라면
				if (check[next_y][next_x][0] == 0)
				{ // 다음 방문한적 x
					if (cur_w == 0)
					{// 현재까지 벽 부순적 없다면
						if (nodes[next_y][next_x] == 1)
						{// 다음이 벽이라면
							wall = 1; //벽 부수고 check
							visit = check[cur_y][cur_x][0] + 1;
							check[next_y][next_x][0] = visit;
							check[next_y][next_x][1] = wall;
							q.push(make_tuple(next_x, next_y, wall));
						}
						if (nodes[next_y][next_x] == 0)
						{//다음이 벽이 아니라면
							wall = 0; //벽 부수지 않고 check
							visit = check[cur_y][cur_x][0] + 1;
							check[next_y][next_x][0] = visit;
							check[next_y][next_x][1] = wall;
							q.push(make_tuple(next_x, next_y, wall));
						}
					}
					else
					{// 현재까지 벽 부순적 있다면
						if (nodes[next_y][next_x] == 0)
						{// 다음에 벽이 없다면 부수지 않고 check
							wall = 1; // 이미 부쉈으므로
							visit = check[cur_y][cur_x][0] + 1;
							check[next_y][next_x][0] = visit;
							check[next_y][next_x][1] = wall;
							q.push(make_tuple(next_x, next_y, wall));
						}
					}
				}
				if (next_x == W - 1 && next_y == H - 1)
				{// 다음이 마지막 노드라면
					if (check[next_y][next_x][0] == 1)
					{//방문을 했던 경우라도
						// 새로운 값이 작으면 작은거로 check
						int now = check[cur_y][cur_x][0] + 1; //현재 노드에서 계산된 값이
						int prev = check[next_y][next_x][0]; // 저장되어있던 값보다
						if (now < prev) check[next_y][next_x][0] = now; // 작다면 작은값으로 초기화
					}
				}
			}
		}
	}
}

int main()
{
	int H, W; // N=X, M=Y
	scanf("%d %d", &H, &W);
	for (int j = 0; j < H; j++)
	{
		for (int i = 0; i < W; i++)
		{
			scanf("%1d", &nodes[j][i]);
		}
	}
	
	bfs(0, 0, W, H);
	
	int result = check[H - 1][W - 1][0];
	if (result)	printf("%d\n", result);
	else printf("-1\n");

	system("pause");
	return 0;
}

gyunghoe 4년 전 4

제가 봤을 때는 두 가지 문제점이 있는 것 같아요.

첫째는 시간 초과의 문제에요. 99번째 줄의 system("pause")때문에 프로그램이 끝나지 않아서 시간초과가 생겨요.

둘째는 방문여부 설정의 문제에요. 위 코드에

4 4

0101

0001

1110

을 입력하면 -1이 나와요. 실제 값은 7이 나와야 해요. 25번째 줄에

cout << cur_y << " , " << cur_x << " with " << cur_w << endl; 코드를 넣어보면

0 , 0 with 0

0 , 1 with 1

1 , 0 with 0

0 , 2 with 1

1 , 1 with 1

2 , 0 with 0

1 , 2 with 1

2 , 1 with 1

3 , 0 with 1

2 , 2 with 1

-1

이런 출력결과가 나오는데요, cost(2,1)지점을 벽을 부수지 않고 갈수 있음에도 벽을 부수고 가는 결과를 최선으로 판정하기 때문에 (3,2) 혹은 (2,3)의 벽을 뚫지 못해요.

이 문제는 예외처리 잘 해서 큐로 풀어도 되지만 덱을 써서 벽을 안뚫는 경우에는 덱의 앞에, 벽을 뚫는 경우에는 덱의 뒤에 원소를 삽입하는 것도 방법이라고 생각해요.

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

문제

문제

출처

ICPC

벽 부수고 이동하기 틀린부분/반례좀 찾아주실 수 있을까요?

stronghsg 4년 전 0

gyunghoe 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말