글 읽기 - 클립보드에서 붙여넣기할때 질문입니다..

baek_su 5년 전 0

bfs와

visited[화면에 있는 글자수 ][클립보드] 방문배열을 이용해서 문제를 풀었습니다.

붙여넣기 부분을 구현할때

큐에 넣어주기전에 방문한적이 있는지와 없는지를 체크하고

그리고

새 화면에 있는 글자수 <= 1000 을 추가해야지 런타임 에러가 안나는데

1010을 넣으면 또 런타임 에러가 뜨네요...

저부분이 어떻게 동작하는지 이해가 잘 안갑니다..

#include <iostream>
#include <queue>


using namespace std;


class Data {
public:
	int monitor;
	int clip;
	int cnt;

	Data() {}
	Data(int a, int b , int c)
	{
		monitor = a;
		clip = b;
		cnt = c;
	}

};

int s;
int visited[2002][2002];//2차원 배열로 모니터와 클립보드의 방문을 표시할거다 
void BFS();

int main()
{
	cin >> s;

	BFS();

	return 0;
}

void BFS()
{
	queue<Data> q;
	q.push(Data(1, 0, 0));//초기의 화면 상태 모니테어 한개의 이모티콘이 있다.
	visited[1][0] = 1;

	while (!q.empty())
	{
		
		int cur_monitor = q.front().monitor;
		int cur_clip = q.front().clip;
		int cur_cnt = q.front().cnt;
	
		q.pop();


		if (cur_monitor == s)
		{
			cout << cur_cnt;
			return;
		}


		
		//화면에서 클립보드로 복사하는 경우
		int n_monitor = cur_monitor;
		int n_clip = cur_monitor;
		
		if (visited[n_monitor][n_clip] == 0)//방문체크
		{
			visited[n_monitor][n_clip] = 1;
			q.push(Data(n_monitor, n_clip, cur_cnt + 1));

		}
		

		//클립보드에서 화면으로 붙여넣는경우
		//0일때는 붙혀넣기를 할 수 없다.
		if (cur_clip > 0)
		{
			 n_monitor = cur_clip + cur_monitor;
			 n_clip = cur_clip;
			
			if (visited[n_monitor][n_clip] == 0 && n_monitor <=1000)//방문체크
			{
				visited[n_monitor][n_clip] = 1;
				q.push(Data(n_monitor, n_clip, cur_cnt + 1));
			}
				
		}

		//화면에서 하나를 빼는경우
		n_monitor = cur_monitor - 1;
		n_clip = cur_clip;
		if (n_monitor > 1)
		{

			if (visited[n_monitor][n_clip] == 0)//방문체크
			{
				visited[n_monitor][n_clip] = 1;
				q.push(Data(n_monitor, n_clip, cur_cnt + 1));

			}
		}
		
			



	}

}

n_monitor <= x에서 x 값이 무엇이든, 이 부분을 검사하기 전에 먼저 visited[n_monitor][n_clip] == 0를 검사하기 때문에, 이 순간의 n_monitor가 2002 이상이라면 배열의 인덱스를 벗어난 접근이 됩니다. <= 1000으로 했을 때 에러가 나지 않는 것은 이때 나올 수 있는 n_monitor의 최댓값이 2000이기 때문이고, 1010으로 하면 2020까지 올라갈 수 있기 때문에 문제가 됩니다.

baek_su 5년 전 0

감사합니다. ㅠㅠ

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

문제

문제

출처

ICPC

클립보드에서 붙여넣기할때 질문입니다..

baek_su 5년 전 0

djm03178 5년 전 2

baek_su 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말