글 읽기 - (말처럼 이동하기) 반례만 찾아주신다면!!

CHULMING 6년 전 0

정말 감사하겠습니다.........

긴 코드 이해하기 쉽게 하려고 최대한 주석 달았습니다.

부탁드립니다..............

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

typedef struct {
	int y, x, day, k; 
    // 행, 열, 이동 횟수, 말처럼 이동할 수 있는 횟수
}Pos;
int map[201][201];
int found[201][201];

int c, r; // r은 세로 , c는 가로
int arr[2][4] = { {0,0,-1,1},{-1,1,0,0} }; // 4방향 이동
int brr[2][8] = { {-1,-2,-2,-1,1,2,2,1},{-2,-1,1,2,-2,-1,1,2} }; // 8방향 이동(말)
int bfs(int k) {
	queue<Pos>que;
	memset(found, -1, 201 * 201); // found는 -1로 초기화
	Pos cur = { 1,1,0,k }; 
    // 출발 지점 (map[1][1] , 현재까지 이동 0, 말처럼 이동가능 횟수 k)
	que.push(cur);
	found[1][1] = k;
    // [1][1] 지점은 k번의 이동횟수를 가진 상태로 방문했었다고 기록
    
	while (!que.empty()) {

		cur = que.front();
		que.pop();
		
		if (cur.y == r && cur.x == c)  // 도착
			return cur.day;
		
		// 원숭이의 이동 (4 방향)
		for (int i = 0; i < 4; i++) {
			int ty = cur.y + arr[0][i];
			int tx = cur.x + arr[1][i];
			if (ty<1 || ty>r || tx<1 || tx>c || found[ty][tx] >= cur.k||
				map[ty][tx]==1)continue;
			// 현재 원숭이가 말처럼 이동할 수 있는 횟수보다 
			// 이전에 이 곳에 방문했을 때 더 많은 횟수를 가졌었다면 방문하지 않음
			
			found[ty][tx] = cur.k; 
			Pos temp = { ty,tx,cur.day + 1,cur.k }; 
			que.push(temp);
		}

		// 말 처럼 이동할 수 있는 횟수가 남아있을 경우 말 처럼 이동 (8 방향)
		if (cur.k > 0) {
			for (int i = 0; i < 8; i++) {
				int ty = cur.y + brr[0][i];
				int tx = cur.x + brr[1][i];
				if (ty<1 || ty>r || tx<1 || tx>c || found[ty][tx] >= cur.k - 1 ||
					map[ty][tx] == 1)continue;
                
				found[ty][tx] = cur.k - 1; 
                // 현재 말 이동 가능 횟수 -1 을 저장 ( 한 번 이동했으므로 )
				Pos temp = { ty,tx,cur.day + 1,cur.k - 1 };
				que.push(temp);
			}
		}

	}
	// 불가능
	return -1;
}
int main() {
	int k;
	scanf("%d %d %d", &k, &c, &r); // 이동횟수, 가로, 세로 순으로 입력
	for (int i = 1; i <= r; i++)
		for (int j = 1; j <= c; j++)
			scanf("%d", &map[i][j]);
	int t = bfs(k);
	
	if (t == -1)printf("-1\n"); // 불가능
	else printf("%d\n", t); // 가능
	return 0;
}

kks227 6년 전 1

memset(found, -1, 201 * 201); // found는 -1로 초기화

18번 줄에서 201*201이 아니라 201*201*sizeof(int)입니다. 세 번째 인자가 원소 수가 아니라 byte 수라서요.

BFS 도중에 found 배열이 제대로 초기화되지 않은 부분에 들어가지 못합니다.

CHULMING 6년 전 1

와... 정말 감사합니다 ㅠㅠㅠ

memset을 자주 사용하는 편이 아니라 아무 생각없이 썼는데 거기에 문제가 있었군요....

덕분에 하나 배웠습니다! 감사합니다~

kks227 6년 전 1

일반 배열(STL이 아닌)을 사용하신다면 아예 sizeof(배열 이름)라고 쓰시면 이런 실수를 예방하실 수 있어요. ㅎㅎ

CHULMING 6년 전 0

아 그렇네요..

한 번 더 감사합니다 .. ㅋㅋㅋㅋㅋ

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

문제

문제

출처

ICPC

(말처럼 이동하기) 반례만 찾아주신다면!!

CHULMING 6년 전 0

kks227 6년 전 1

CHULMING 6년 전 1

kks227 6년 전 1

CHULMING 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말