[백준] 10157- 자리배정 (C++)

문제 출처 :

www.acmicpc.net/problem/10157

10157번: 자리배정

문제 풀이:

• 앞서 포스팅한 Python 편에 써놓았다.
• 실제로 python으로 문제를 풀고 Logic을 그대로 하여 C++로 풀었다.

#include <iostream>
#include <vector>

using namespace std;

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 }; 

int maps[1000][1000] = { 0, };
void print_maps(int r, int c)
{
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cout << maps[i][j] << " ";
		}
		cout << '\n';
	}
}

int main()
{
	int c, r, k;

	cin >> c >> r >> k;

	if (k > r * c)
	{
		cout << 0;
		return 0;
	}

	if (k == 1)
	{
		cout << 1 << " " << 1 << endl;
		return 0;
	}

	int cnt = 2;
	int s_x = 0;
	int s_y = 0;
	maps[s_x][s_y] = 1;
	vector <int> x_stack = {};
	vector <int> y_stack = {};

	int dir = 0;
	bool loop_break = false;
	maps[s_x][s_y] = 1;
	x_stack.push_back(s_x);
	y_stack.push_back(s_y);
	//char tmp;
	while (true) {
		//cin >> tmp;
		while (!x_stack.empty() && !y_stack.empty())
		{
			s_x = x_stack.back();
			s_y = y_stack.back();
			x_stack.pop_back();
			y_stack.pop_back();
			int nx = s_x + dx[dir];
			int ny = s_y + dy[dir];
			if (nx >= r || nx < 0 || ny >= c || ny < 0)
			{
				continue;
			}
			if (maps[nx][ny] != 0)
			{
				continue;
			}
			//cout << nx << " " << ny << " " << cnt << endl;
			//print_maps(r, c);
			maps[nx][ny] = cnt;
			if (cnt == k)
			{
				cout << ny + 1 << " " << nx + 1 << endl;
				loop_break = true;
				break;
			}
			x_stack.push_back(nx);
			y_stack.push_back(ny);
			cnt += 1;

			
		}
		x_stack.push_back(s_x);
		y_stack.push_back(s_y);
		if (dir == 0) dir = 1;
		else if (dir == 1) dir = 2;
		else if (dir == 2) dir = 3;
		else dir = 0;
		if (loop_break)
		{
			break;
		}
	}
	return 0;
}

 

• 생각해볼점
  • python와 C++의 실행속도에 엄청난 차이가 있다는 걸 체감할 수 있었다. Python, pypy3 ,c++로 모두 돌려본 결과 python은 시간초과날까봐 정말 조마조마하게 올라간다.. 마치 내가 등산할때 처럼 낑낑 거리면서 된다면 C++은 같은 로직임에도 불구하고 정말 훨씬 빠르다.. 대부분의 PS에서 C++를 쓰는 이유를 알겟다.
  • 사진에서 시간초과는 k=1 일때의 예외처리를 안해주어서 났다. 코드에서 while문을 true로 해놓고 돌리는데 k=1일때를 넣지 않아서 while문을 빠져나오지 못하여 시간초과가 났다. 틀렷습니다 가 아닌 시간초과라는 점을 주의깊게 보아야겠다.

C++, Python, pypy3 실행시간 비교