글 읽기 - [7562,나이트의 이동] 고해성사..

beomyoung93 2년 전 1

원래 계속 시간초과나서 2시간정도 헤매고 질문글 올리려다가, 같은 BFS문제(7576-토마토) 풀었던거에서 힌트 얻어서 결국 풀었습니다 ㅠㅠ

인수 전달방식이나 초기화 방법이 무식하긴 한데, 역시 이정도급 난이도 문제들에서는 다른 것들을 의심하기보다는 내가 짠 소스 로직을 의심하는게 맞는것 같습니다.

#include<stdio.h>
#include<queue>
#define FALSE 0
#define TRUE 1
#define SIZE 300

using namespace std;
typedef struct {
	int row;
	int col;
}point;
int visited[SIZE][SIZE];
int dRow[] = { -1, -2, -2, -1, 1, 2,  2,  1 };	//10시, 11시, 1시, 2시, 4시, 5시, 7시, 8시 방향
int dCol[] = { -2, -1,  1,  2, 2, 1, -1, -2 };  //10시, 11시, 1시, 2시, 4시, 5시, 7시, 8시 방향
int L;			//한 변의 길이
point from, to;	//현재 있는 칸, 이동하려고 하는 칸

bool isOver(point p);
void initVisited(int n);
int BFS(queue<point> q);

int main() {
	int T;	//테스트케이스 개수
	queue<int> result;

	//입력
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		queue<point> param;

		scanf("%d", &L);
		scanf("%d %d", &from.row, &from.col);
		scanf("%d %d", &to.row, &to.col);

		//처리
		initVisited(L);		//초기화

		visited[from.row][from.col] = TRUE;
		if (from.row == to.row && from.col == to.col) {		//처음부터 목적지인 경우..
			result.push(0);
		}
		else {
			for (int i = 0; i < 8; i++) {
				/*
				1. 범위를 벗어나지 않고
				2. 방문하지 않았다면
				*/
				if (!isOver({ from.row + dRow[i], from.col + dCol[i] }) &&
					visited[from.row + dRow[i]][from.col + dCol[i]] == FALSE) {

					visited[from.row + dRow[i]][from.col + dCol[i]] = TRUE;
					param.push({ from.row + dRow[i], from.col + dCol[i] });
				}
			}
			result.push(BFS(param));
		}

	}
	//출력
	for (int t = 0; t < T; t++) {
		printf("%d", result.front());	result.pop();
		if (t != T - 1) {
			printf("\n");
		}
	}

	return 0;
}

bool isOver(point p) {
	return (p.row < 0 || L <= p.row || p.col < 0 || L <= p.col) ? TRUE : FALSE;
}
void initVisited(int n) {
	for (int r = 0; r < n/*L*/; r++) {
		for (int c = 0; c < n/*L*/; c++) {
			visited[r][c] = FALSE;
		}
	}
}
int BFS(queue<point> q) {
	queue<point> que;		//전체 큐
	queue<point> queOnce;	//n번째 접근가능한 위치를 담은 큐
	point tmp;
	int result = 1;			//처음부터 from == to  인 케이스는 main()에서 이미 처리됨

	que = q;
	while (!que.empty()) {

		queOnce = que;

		/*★★★ 
		n번째 위치만 처리할 queOnce로 복사할때 이미 처리한 que를 제외( que.pop() )해야하는데, 이거 안하면 전체큐인 que에 쌓기만 함.
		이러면 나중에 체스판 크기가 커질수록 queOnce로 복사할 전체큐(=que)가 커지고, 그만큼 매번 검사할 queOnce도 커져서
		66%에서 시간초과 발생
		★★★*/
		while (!que.empty()) {		
			que.pop();
		}


		//n번째 이동들을 처리하는 while문
		while (!queOnce.empty()) {
			tmp = queOnce.front();		queOnce.pop();
			visited[tmp.row][tmp.col] = TRUE;

			if (tmp.row == to.row && tmp.col == to.col) {		//목적지에 도달하면
				return result;
			}
			for (int i = 0; i < 8; i++) {						//목적지에 도달하지 않았다면..
				/*
				1. 범위를 벗어나지 않고
				2. 방문하지 않았다면
				*/
				if (!isOver({ tmp.row + dRow[i], tmp.col + dCol[i] }) &&
					visited[tmp.row + dRow[i]][tmp.col + dCol[i]] == FALSE) {

					visited[tmp.row + dRow[i]][tmp.col + dCol[i]] = TRUE;
					que.push({ tmp.row + dRow[i], tmp.col + dCol[i] });		//다음 후보 위치를 큐에 push
				}
			}
		}
		result++;	//n번째 이동들을 처리하는 단위를 벗어나면 n+1번째 이동이 됨
	}

	return result;
}

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

문제

문제

출처

ICPC

[7562,나이트의 이동] 고해성사..

beomyoung93 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말