C++ / 백준 / 2641 / 다각형그리기

문제

 

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

2641번: 다각형그리기

 

문제풀이

 

구현문제이다. DFS로 풀었다.

모양수열의 길이는 최대 50이므로 100*100 크기의 2차원 배열을 선언하여 풀었다.

문제의 예시를 보면 모양을 회전 또는 뒤집어서는 안 되며, 주어진 모양과 같아야 한다.

 

DFS함수로 2차원 배열에 입력받은 표본 모양수열의 값들대로 이동하면서 값을 true로 바꾼다.

DFS함수가 종료되면 M번만큼의 표본 모양수열과 같은 길이의 모양수열의 값들을 입력받으면서 해당 경로가 있는지를 판별한다.

 

void DFS(int y, int x, int cnt, string route) {	
	if (cnt == N) {		
		path.insert(route);
		return;
	}
	for (int idx = 0; idx < 4; ++idx) {
		int ny = y + dy[idx];
		int nx = x + dx[idx];
		if (visited[ny][nx] == false) continue;
		visited[ny][nx] = false;
		DFS(ny, nx, cnt + 1, route + to_string(idx + 1));
		visited[ny][nx] = true;
	}	
}

DFS함수 인자로는 y, x, 현재 이동한 칸 개수, 이동한 방향들을 저장하는 string으로 구성된다.

만약 표본 모양수열의 길이만큼 이동했으면, 해당 경로를 set인 path에 입력한다.

그렇지 않다면 현재 위치(y, x)에서 이동할 수 있는 칸으로 이동한다.

 

	vector<string>answer;
	for (int idx = 0; idx < M; ++idx) {
		string str("");
		for (int idx2 = 0; idx2 < N; ++idx2) {
			cin >> input;
			str += input;
		}
		if (path.find(str) != path.end()) {
			answer.push_back(str);
		}
	}

표본 모양수열의 길이와 같은 모양수열을 입력받고, path에서 해당 경로가 있는지를 확인한다.

있다면 answer에 push_back 한다.

 

모든 입력이 종료되면 answer의 개수와, answer[0]부터 끝까지 모든 경로를 출력하면 된다.

 

코드

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

bool visited[100][100];

set<string>path;
int N;
int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

void DFS(int y, int x, int cnt, string route) {	
	if (cnt == N) {		
		path.insert(route);
		return;
	}
	for (int idx = 0; idx < 4; ++idx) {
		int ny = y + dy[idx];
		int nx = x + dx[idx];
		if (visited[ny][nx] == false) continue;
		visited[ny][nx] = false;
		DFS(ny, nx, cnt + 1, route + to_string(idx + 1));
		visited[ny][nx] = true;
	}	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	char input(' ');
	string origin("");
	for (int idx = 0; idx < N; ++idx) {
		cin >> input;
		origin += input;
	}

	int M(0);
	cin >> M;

	int y = 50;
	int x = 50;

	for (int idx = 0; idx < N; ++idx) {
		int dir = origin[idx] - '0' - 1;
		y += dy[dir];
		x += dx[dir];
		visited[y][x] = true;
	}

	for (y = 0; y < 100; ++y) {
		for (x = 0; x < 100; ++x) {
			if (visited[y][x] == true) {
				DFS(y, x, 0, "");
			}
		}
	}

	vector<string>answer;
	for (int idx = 0; idx < M; ++idx) {
		string str("");
		for (int idx2 = 0; idx2 < N; ++idx2) {
			cin >> input;
			str += input;
		}
		if (path.find(str) != path.end()) {
			answer.push_back(str);
		}
	}

	cout << answer.size() << '\n';
	for (int path_idx = 0; path_idx < answer.size(); ++path_idx) {
		for (int idx = 0; idx < answer[path_idx].size(); ++idx) {
			cout << answer[path_idx][idx] << ' ';
		}
		cout << '\n';
	}
}