C++ / 백준 / 3108 / 로고

문제

https://www.acmicpc.net/problem/3108

3108번: 로고

문제풀이

문제를 잘못 본 것도 있고 무작정 코드를 짜다가 길어지고 복잡해져서 다른 풀이를 참조하여 풀었다.

구현부를 크게 두 가지로 나눌 수 있다.

첫 번째는 좌표를 입력받아 2차원 벡터를 선언하고 해당 좌표에 표시하기,

두 번째는 DFS이다.

문제에서 전진, 회전 이런 건 무시하고 연필을 올리는 명령어인 PU명령어에만 집중하면 된다.

먼저 좌표는 -500부터 500까지 있으니 크기는 1000이다.

하지만 위 그림처럼 좌표가 찍히면 (2,2)와 (3,2)는 연결이 되지 않으므로 연필을 올려야 한다.

이걸 2차원 벡터로 만들기 위해서는 좌표에 2배를 하여 나타내야 한다.

그리고 벡터는 -500이란 위치가 없으므로 0~1000으로 나타내야 한다.

둘을 합치면 0~2000까지의 크기를 가진 2차원 벡터를 만들면 된다.

따라서 값을 입력받고, 그 값에 500을 더하고 2를 곱하여 직사각형을 그린다.

true값은 선이 있다는 거고 false는 선이 없다는 의미이다.

그다음 DFS를 실행하면 된다.

100번 회전을 하든 100칸을 걷든 연필을 올리는 횟수만 구하므로 DFS에서는 선이 있는 곳만 찾아서 실행하면 된다.

그리고 마지막으로 문제에서 거북이는 (0, 0)에서 시작하므로 (0+500)*2의 값인 1000부터 시작한다 보면 된다.

메인 문에서 DFS함수를 실행할 때마다 answer의 값에 1을 더하여 연필을 드는 횟수를 구한다.

(1000, 1000)이 직사각형에 포함되어있다면 처음에 연필을 들 필요가 없으므로 -1부터 값을 더하면 되고,

포함되어있지 않다면 그대로 두면 된다.

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>>loc = { {-1,0},{1,0},{0,-1},{0,1} };
vector<vector<bool>>board(2001, vector<bool>(2001, false));

void DFS(int y, int x) {
	board[y][x] = false;
	int idx = 0;
	for (idx = 0; idx < 4; ++idx) {
		int n_y = y + loc[idx][0];
		int n_x = x + loc[idx][1];
		if (n_y >= 0 && n_y <= 2000 && n_x >= 0 && n_x <= 2000)
			if (board[n_y][n_x]) DFS(n_y, n_x);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0;
	int idx = 0;
	cin >> N;
	int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
	int y = 0, x = 0;

	for (idx = 0; idx < N; ++idx) {
		cin >> x1 >> y1 >> x2 >> y2;

		x1 = (x1 + 500) * 2;
		x2 = (x2 + 500) * 2;
		y1 = (y1 + 500) * 2;
		y2 = (y2 + 500) * 2;

		for (x = x1; x <= x2; ++x) {
			board[y1][x] = true;
			board[y2][x] = true;
		}
		for (y = y1; y <= y2; ++y) {
			board[y][x1] = true;
			board[y][x2] = true;
		}
	}

	int answer = 0;

	if (board[1000][1000] == 1) answer = -1;
	for (y = 0; y <= 2000; ++y) {
		for (x = 0; x <= 2000; ++x) {
			if (board[y][x]) {
				++answer;
				DFS(y, x);
			}
		}
	}
	cout << answer;
}