글 읽기 - 틀린 케이스를 못찾겠네요;

na982 7년 전 0

심플하게 bfs로 탐색하는 로직입니다.;

문제 및 질문 란에 있는 셈플 답안은 모두 정상적으로 나오는데; 안되네요;

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;

typedef struct{
	int y, x;
	int cnt, block;
}DATA;

int n, m;
int map[1002][1002], visited[1002][1002];

//상 하 좌 우
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

int main()
{
	scanf("%d %d", &n, &m);
	memset(visited, 0, sizeof(visited));
	memset(map, -1, sizeof(map));
	for (int y = 1; y <= n; ++y){
		for (int x = 1; x <= m; ++x){
			scanf("%1d", &map[y][x]);
		}
	}

	queue<DATA> q;
	DATA data;
	data.y = 1, data.x = 1;
	data.cnt = 1, data.block = 1;
	q.push(data);
	while (!q.empty()){
		DATA here = q.front();
		if (here.y == n && here.x == m){
			printf("%d\n", here.cnt);
			break;
		}
		q.pop();

		DATA there;
		for (int dir = 0; dir < 4; ++dir){
			if (map[here.y + dy[dir]][here.x + dx[dir]] == 0 && visited[here.y + dy[dir]][here.x + dx[dir]] == 0){
				visited[here.y + dy[dir]][here.x + dx[dir]] = 1;
				there.y = here.y + dy[dir];	there.x = here.x + dx[dir];
				there.cnt = here.cnt + 1;	there.block = here.block;
				q.push(there);
			}
		}

		for (int dir = 0; dir < 4; ++dir){
			if (map[here.y + dy[dir]][here.x + dx[dir]] == 1 && here.block == 1 && visited[here.y + dy[dir]][here.x + dx[dir]] == 0){
				visited[here.y + dy[dir]][here.x + dx[dir]] = 1;
				there.y = here.y + dy[dir];	there.x = here.x + dx[dir];
				there.cnt = here.cnt + 1;	there.block = 0;
				q.push(there);
			}
		}
	}
	if (q.empty()){
		printf("-1\n");
	}
	return 0;
}

ainch96 7년 전 1

맨 처음 (1,1)을 삽입 할 때 visited[1][1] = 1 해줘야 하지 않나요?

na982 7년 전 0

그부분이 빠졌네요; 하지만 수정해도; 오답이라고 나오네요;

ainch96 7년 전 3

저도 틀린 점 막 고쳐 보느라고 수정한 소스가 더럽긴 한데.... 아래 처럼 수정하면 됩니다.

그 이유는 동일한 점에 도달한 거리가 동일하더라도 벽을 부수고 온 경우보다 벽을 부수지 않고 온 경우가 더 나아갈 가능성이 높기 때문에

둘 경우를 구별 해줘야 하기 때문입니다.

2 4

0111

0010

이런 예시가 있다면 (1,1)->(2,1)->(2,2)->(2,3)->(2,4)으로 도착이 가능 합니다.

하지만 기존의 코드로 하면 만약에 (1,1)->(1,2)->(2,2)으로 해서 visited[2][2]를 먼저 채워 버리면 위의 정답 예시 경로가 (2,2)를 지나지 못해서 -1을 출력해 버립니다. 그래서 이 두 경우를 구별해줘야 하는 겁니다.

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;

const int MAX = 1002;

typedef struct DATA{
	int y, x;
	int cnt, block;
	DATA(int a, int b,int c,int d){
		y = a, x = b;
		cnt = c, block = d;
	}
	DATA(){}
}DATA;

int n, m;
int map[1002][1002], visited[1002][1002][2];

//상 하 좌 우
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

int main()
{
	scanf("%d %d", &n, &m);
		
	memset(map, -1, sizeof(map));
	for (int y = 1; y <= n; ++y){
		for (int x = 1; x <= m; ++x){
			scanf("%1d", &map[y][x]);
		}
	}

	queue<DATA> q;
	q.push(DATA(1, 1, 1, 1));
	visited[1][1][1] = 1;
	//block : 앞으로 더 지나갈 수 있는 블록의 개수.
	bool possi = false;
	while (!q.empty()){
		DATA here = q.front();
		if (here.y == n && here.x == m){
			possi = true;
			printf("%d\n", here.cnt);
			break;
		}
		q.pop();
		

		for (int dir = 0; dir < 4; ++dir){
			int ny = here.y + dy[dir];
			int nx = here.x + dx[dir];
			if (here.block == 1){
				if (map[ny][nx] == 0 && visited[ny][nx][1] == 0){
					visited[ny][nx][1] = 1;
					q.push(DATA(ny,nx,here.cnt+1,1));
					continue;
				}
				else if (map[ny][nx] == 1 && visited[ny][nx][0]==0){
					visited[ny][nx][0] = 1;
					q.push(DATA(ny,nx,here.cnt+1,0));
					continue;;
				}
				
			}
			else{
				if (map[ny][nx] == 0 && visited[ny][nx][0] == 0){
					visited[ny][nx][0] = 1;
					q.push(DATA(ny, nx, here.cnt + 1, 0));
				}
			}
		}
	}
	if (possi == false){
		printf("-1\n");
	}
	return 0;
}

ainch96 7년 전 1

근데 맞추고 다른 분들 소스 읽으니까 제 소스가 엄청 별로군요... 일단 맞추시고 더 좋은 소스 읽으세요 ..ㅠㅠ

na982 7년 전 1

@pinch3773 님 많이 배우고 갑니다. 감사합니다.

wjddms206 7년 전 1

pinch3773

덕분에 많이 배웠습니다. 감사합니다.

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

문제

문제

출처

ICPC

틀린 케이스를 못찾겠네요;

na982 7년 전 0

ainch96 7년 전 1

na982 7년 전 0

ainch96 7년 전 3

ainch96 7년 전 1

na982 7년 전 1

wjddms206 7년 전 1

pinch3773

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말