글 읽기 - 질문게시판에서 줍줍한 반례를 써도 맞는데 틀린다고 나와서 질문올립니다

antjddlekd 4년 전 0

여러 저스스로 반례도 찾아보고 bfs 단계 카운팅하는 방법도 바꿔가면서(chk로 카운팅->구조체로 만든 자료형에 변수추가)해봤는데 로컬에서는 모두 답이 뜨고제출시에는 단호박으로 틀렸다네요 ㅠㅠ 입출력의 문제인가 싶으면 그 동안 풀었던 문제와 같은 방법으로 입출력을 했는데 왜그런가 싶습니다 고수 분들의

조언 부탁드립니다 ㅠㅠ

대략적인 로직을 설명드리면

맵을 입력받으면서 pair<int,int>자료형에 B 3개 E 3개를 저장해놓고 중점값만 X,Y,STATUS(누워있는지 서있는지)정보를 저장하고 큐에 넣었습니다
BFS로직내에서의 작동은 1)E중점값과 현재 참조한 q.front값이 같으면 ans에 값을 저장하고 break 2)서있는지 (status=1) 누워있는지에 따라 분기를 나누어 또 그 내부에는 위. 아래, 오른쪽, 왼쪽, turn을 시켰습니다(여기엔 문제가 거의 없어보이는 것이 일일이 chk값을 출력해서 노드마다 추적해봤습니다)
그리고 ans 를 출력합니다

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int N;
char map[51][51];
int chk[2][51][51];
pair<int, int> init_B[3], init_E[3];	//처음에 B,E정보 담는 곳
struct node {
	int x;
	int y;
	bool status;		//누워있는지 서있는지		서있는게 true
	int cnt;			//BFS 노드 단계 카운팅
};
node tmpB;	//통나무 중점	
node tmpE;	//목적지 중점
int main() {
	cin >> N;
	int bidx = 0, eidx = 0;
	for (int i = 0; i < N; i++) {	//입력 받으면서 B,E정보 저장
		for (int j = 0; j < N; j++) {
			cin >> map[j][i];
			if (map[j][i] == 'B') {
				init_B[bidx] = { j,i };
				map[j][i] = '0';
				bidx++;
			}
			else if (map[j][i] == 'E') {
				init_E[eidx] = { j,i };
				map[j][i] = '0';
				eidx++;
			}
		}
	}
	//받은 B,E정보를 여기서 가공해서 만들어놓은 node자료형에 넣음
	if (init_B[1].first == init_B[0].first) tmpB = {init_B[1].first,init_B[1].second,1,0};
	else tmpB = { init_B[1].first,init_B[1].second,0 ,0};
	if (init_E[1].first == init_E[0].first) tmpE = { init_E[1].first,init_E[1].second,1,0};
	else tmpE = { init_E[1].first,init_E[1].second,0 ,0};
	queue<node> q;
	q.push(tmpB);
	int ans = 0;
	while (!q.empty()) {
		int x = q.front().x, y = q.front().y;
		bool status = q.front().status;
		int tcnt = q.front().cnt;
		q.pop();
		
		if (x == tmpE.x && y == tmpE.y && status == tmpE.status) {	//도착시 상태도 같아야
			ans = tcnt;
			break;
		}
		if (status) {//서있을때 status=1
			if (y - 2 >= 0 && !chk[1][x][y - 1] && map[x][y - 2] != '1') {//U
				q.push({ x,y - 1,1,tcnt+1 });
				chk[1][x][y - 1] = tcnt + 1;
			}
			if (y + 2 < N && !chk[1][x][y + 1] && map[x][y + 2] != '1') {//D
				q.push({ x,y + 1,1,tcnt+1 });
				chk[1][x][y + 1] = tcnt + 1;
			}
			if (x + 1 < N && !chk[1][x + 1][y] && map[x + 1][y] != '1' && map[x + 1][y - 1] != '1' && map[x + 1][y + 1] != 1) {//R
				q.push({ x + 1,y,1,tcnt+1 });
				chk[1][x + 1][y] = tcnt + 1;
			}
			if (x - 1 >= 0 && !chk[1][x - 1][y] && map[x - 1][y] != '1' && map[x - 1][y - 1] != '1' && map[x - 1][y + 1] != '1') {//L
				q.push({ x - 1,y,1,tcnt+1 });
				chk[1][x - 1][y] = tcnt + 1;
			}
			if (x - 1 >= 0 && x + 1 < N && !chk[0][x][y] && map[x - 1][y] != '1' && map[x - 1][y - 1] != '1' && map[x - 1][y + 1] != '1' && map[x + 1][y] != '1' && map[x + 1][y - 1] != '1' && map[x + 1][y + 1] != '1') {
				q.push({ x,y,0,tcnt+1 });
				chk[0][x][y] = tcnt + 1;
			}
		}
		else {
			if (y - 1 >= 0 && !chk[0][x][y - 1] && map[x][y - 1] != '1' && map[x - 1][y - 1] != '1' && map[x + 1][y - 1] != '1') {//U
				q.push({ x,y - 1,0 ,tcnt+1});
				chk[0][x][y-1] = tcnt + 1;
			}
			if (y + 1 < N && !chk[0][x][y + 1] && map[x][y + 1] != '1' && map[x - 1][y + 1] != '1' && map[x + 1][y + 1] != '1') {//D
				q.push({ x,y + 1,0 ,tcnt+1});
				chk[0][x][y + 1] = tcnt + 1;
			}
			if (x + 2 < N && !chk[0][x + 1][y] && map[x + 2][y] != '1') {//R
				q.push({ x + 1,y,0,tcnt+1 });
				chk[0][x + 1][y] = tcnt + 1;
			}
			if (x - 2 >= 0 && !chk[0][x - 1][y] && map[x - 2][y] != '1') {//L
				q.push({ x - 1,y,0 ,tcnt+1});
				chk[0][x - 1][y] = tcnt + 1;
			}
			if (y - 1 >= 0 && y + 1 < N && !chk[1][x][y] && map[x][y - 1] != '1' && map[x - 1][y - 1] != '1' && map[x + 1][y - 1] != '1' && map[x][y + 1] != '1' && map[x - 1][y + 1] != '1' && map[x + 1][y + 1] != '1') {
				q.push({ x,y,1 ,tcnt+1});
				chk[1][x][y] = tcnt + 1;
			}
		}
	}
	cout << ans ;
	return 0;
}

antjddlekd 4년 전 0

멍청했네요 딱하나 '1'이 1이어서 틀린거였네요

반성하는의미로 글남겨둡니다 여러분 저같이 멍청하지 마세요!

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

문제

문제

출처

ICPC

질문게시판에서 줍줍한 반례를 써도 맞는데 틀린다고 나와서 질문올립니다

antjddlekd 4년 전 0

antjddlekd 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말