글 읽기 - 틀린 테스트케이스가 있을까요?

ksjin123s 5년 전 0

안녕하세요.

질문 게시판을 통하여 전부 읽어보았으나,

게시판에서 앞서 언급된 모든 테스트케이스의 정답을 출력합니다.

하지만 제출시 틀렸다고 나옵니다.

혹여 제가 놓친부분이 있다면 알려주시면 감사하겠습니다.

잘못된 테스트케이스의 경우라도 잡아주시면 감사합니다.

[코드설명]

Queue를 이용한 BFS를 구현하였구요.

visit배열은 벽을 아직 뚫지 않은 방문배열이고,

visit_punch는 벽을 이미 뚫어버린 방문 배열입니다.

while문 안쪽에서는

if(값이 유효하면)

2. if(뚫을 필요가없고, 벽을 뚫지 않은 방문배열이나, 벽을 뚫어버린 방문 배열이 아직 비어있다면)

3. if(벽을 뚫을 수 있는 방문배열)

3. else if (벽을 뚫어버린 방문배열)

2. else if(뚫어야 하고, 벽을 뚫어버린 방문 배열이 아직 비어있으며, 뚫을 수 있으면)

이런식으로 코딩했습니다.

마지막 도착 시, 벽을 뚫은것과 안뚫은 여부와 관계 없이 도착만 한다면 더 적은 횟수로 도착한 값을 출력했습니다.

#include <stdio.h>
#include <stdlib.h>

int x, y;
int mat[1001][1001] = { 0, };

int visit[1001][1001] = { 0, };
int visit_punch[1001][1001] = { 0, };

int a[4] = { -1,0, 1, 0 };
int b[4] = { 0,1,0,-1 };

typedef struct queue {
	int x;
	int y;
	int punch;
}queue;

queue q[1000001] = { 0, };

int isvalid(int first, int second) { //유효값 검사
	if (first < 1 || first > x || second < 1 | second > y) return 0;
	else return 1;
}
void BFS(int first, int second)
{
	int front = 1;
	int rear = 0;
	int f, s, p;
	int min, max;
    
    // 첫번째 큐 삽입
	q[rear].x = first; //x좌표
	q[rear].y = second; //y좌표
	q[rear].punch = 1;  // 뚫을 수 있음
	visit[first][second] = 1; //뚫을 수 있는 방문배열

    // BFS
	while (rear < front) {
		for (int i = 0; i < 4; i++) {
			f = q[rear].x + a[i];
			s = q[rear].y + b[i];
			p = q[rear].punch;

			if (isvalid(q[rear].x + a[i], q[rear].y + b[i])) {
				if (mat[f][s] == 0 && (visit[f][s] == 0 || visit_punch[f][s] == 0)) {
					if (q[rear].punch == 1 && visit[f][s] == 0) {
						visit[f][s] = visit[q[rear].x][q[rear].y] + 1;
						q[front].x = f;
						q[front].y = s;
						q[front].punch = p;
						front++;
					}
					else if (q[rear].punch == 0 && visit_punch[f][s] == 0) {
						visit_punch[f][s] = visit_punch[q[rear].x][q[rear].y] + 1;
						q[front].x = f;
						q[front].y = s;
						q[front].punch = p;
						front++;
					}

				}
				else if (mat[f][s] == 1 && visit_punch[f][s] == 0 && p) {
					q[front].x = f;
					q[front].y = s;
					q[front].punch = p - 1;
					visit_punch[f][s] = visit[q[rear].x][q[rear].y] + 1;
					front++;
				}
			}
		}
		rear++;
	}

    // 출력부분
	min = visit_punch[x][y];
	max = visit[x][y];

	if (min > 0 && max > 0) {
		if (min < max) printf("%d", min);
		else printf("%d", max);
	}
	else if (min > 0 || max > 0) {
		if (min > 0) printf("%d", min);
		else printf("%d", max);
	}
	else printf("-1");
}

int main() {
    //입력부분
	scanf("%d %d", &x, &y);

	for (int i = 1; i <= x; i++)
		for (int j = 1; j <= y; j++)
			scanf("%1d", &mat[i][j]);

    // 첫칸과 끝칸이 1인 경우 -1 출력
	if (mat[1][1] == 1 || mat[x][y] == 1) { printf("-1");  return 0; }
    
	BFS(1, 1);

	return 0;
}

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