상경한 개발자 지망생들

문제 링크

www.acmicpc.net/problem/1937

접근 방법

 간략히 말하자면 2차원 배열 위에서 현재 값 보다 더 큰 값으로만 이동할 수 있을 때, 가장 멀리 이동 할 수 있는 거리를 구하는 문제이다. 단, 출발점이 정해져 있지 않아 모든 위치에서 출발을 시작 해 봐야 한다. 

 하지만, 동적계획법을 사용하여 많은 계산을 줄일 수 있다 어떻게 줄일 수 있을까?

아래의 그림을 보자!

예를 들어, 9에서 11로 이동한 경우와 5에서 11로 이동한 경우 모두 11에서 부터 끝 까지의 경우의 수는 같다는 것을 알 수 있다. 9 -> 11 -> 15 , 5 -> 11 -> 15, 즉 어떤 위치 부터 끝 까지의 값을 기록하면 중복되는 연산을 줄일 수 있다는 것이다.

dp[세로][가로]로 표현하여 기록할 수 있다.  

pair<int, int> nextdir[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

for (int i = 0; i < 4; i++) {
		int next_x = nowx + nextdir[i].first;
		int next_y = nowy + nextdir[i].second;
		if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
			if (map[nowx][nowy] < map[next_x][next_y]) {
				ret = max(ret, solve(next_x, next_y));
			}
		}
	}
dp += ret;
return dp;

가장 오래 살아남아야 하므로, 위의 코드를 보면 상,하,좌,우 4방향으로 이동했을 때 최댓값을 갱신하도록 하여, 현재의 생존일에 더하도록 하였다.   

소스 코드

#include <iostream>
#include <algorithm>

using namespace std;

int map[500][500];
int dp[500][500];
pair<int, int> nextdir[4] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
int result = 0;
int n;

int solve(int nowx, int nowy) {

	int &ref = dp[nowx][nowy];
	int ret = 0;

	if (ref != 0)  //방문한 적이 있다면
		return ref;
	else  // 방문한적이 없다면
		ref = 1;

	for (int i = 0; i < 4; i++) {
		int next_x = nowx + nextdir[i].first;
		int next_y = nowy + nextdir[i].second;
		if (0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
			if (map[nowx][nowy] < map[next_x][next_y]) {
				ret = max(ret, solve(next_x, next_y));
			}
		}
	}
	ref += ret;
	return ref;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			if (dp[i][j] == 0) //방문 한적 없다면
				result = max(result, solve(i, j));
			else //방문한 적 있다면
				result = max(result, dp[i][j]);
		}

	cout << result << endl;
}

문제 링크

www.acmicpc.net/problem/2193

접근 방법

 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

문제의 조건에서 알 수 있는 점 들이 있다.

1. 처음 시작은 무조건 1이어야 한다.

2. 1다음엔 0이어야 한다.

3. 0 다음엔 0또는 1이어야 한다.

그럼 dp 테이블은 어떻게 설계해야 할까? 다음 그림을 보자

5자리 수일 때 규칙에 따라 표현하면 이런 트리가 형성 될 것이다. dp는 중복된 연산을 줄이는 것이 핵심이다. 그림을 보았을 때 어떤 부분이 중복되는지 쉽게 찾을 수 있다.

 위의 그림에서 같은 층(자릿수)의 같은 값을 가진 (층:4 값:0) 노드 부터는 자식 노드들의 갯수가 완전히 일치하는 것을 알 수 있다. 

 즉 층(자릿수)과 값(0또는1) 2가지 특성을 사용한 2차원 DP 테이블을 사용해야 된다는 유추를 할 수 있다.

dp[자릿수][값=2]

소스 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
long long dp[100][2];

long long solve(int cnt, int now) {

	long long &ref = dp[cnt][now];

	if (ref != 0)  //방문한적 있다면
		return ref;
	if (cnt == n)  //마지막까지 도달
		return ref = 1;
	if (now) 
		ref += solve(cnt + 1, !now);
	else 
		ref += (solve(cnt + 1, now) + solve(cnt + 1, !now));
	return ref;
}

int main() {
	cin >> n;
	cout  << solve(1, 1) << endl;
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

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

접근 방법

(1) 문제에서 제시하는 2048게임은 한 턴에 동, 서, 남, 북 4방향 중 1방향으로 이동이 가능하고, 최대 5번 이동이 가능하므로, 4^5 = 1024가지의 경우의 수가 존재한다. 1024번의 경우의 수를 탐색하기 위해 백트래킹(DFS)기법을 사용하여 최댓값을 도출하면 된다.

(2) 어떤 방향으로 이동을 시킬 때, 3가지 단계로 구분하였다. 

 1. 한쪽으로 모든 숫자를 몰아넣는다.(예시: 서쪽 방향)

 2. 이동시킨 방향(서쪽)의 끝을 기준으로 시작하여 인접한 수가 같으면 합친다.

 3. 다시 이동시킨 방향으로 몰아 넣는다.

이런 과정을 거치면 한 쪽 방향에 대한 이동이 끝난다.

(3) (2)의 과정에 대한 소스 코드

// 서쪽으로 이동 시킬때의 예시
for (int i = 0; i < n; i++) {
	int zerocnt = 0; //빈 공간의 갯수를 새기 위한 변수 -> 수를 몇칸 이동시킬지 결정
    //1번 과정
	for (int j = n - 1; j >= 0; j--) {
		if (map[i][j] == 0) { //빈 공간일 때
			zerocnt++;
		}
		else { //빈 공간이 아닐 때
			if (zerocnt != 0) {
				map[i][j + zerocnt] = map[i][j];
				map[i][j] = 0;
			}
		}
	}
    // 2번 과정
	for (int j = n - 1; j > 0; j--) {
		if (map[i][j - 1] == map[i][j]) { //인접한 숫자가 같다면
			map[i][j] *= 2; 
			map[i][j - 1] = 0;
		}
	}
    // 3번 과정
	zerocnt = 0;
	for (int j = n - 1; j >= 0; j--) {
		if (map[i][j] == 0) {
			zerocnt++;
		}
		else {
			if (zerocnt != 0) {
				map[i][j + zerocnt] = map[i][j];
				map[i][j] = 0;
			}
		}
	}
}

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, result;

vector<vector<int>> move(int dir, vector<vector<int>> map) { //0 북 1 서 2 동 3 남
	if (dir == 0) {
		for (int j = 0; j < n; j++) {
			int zerocnt = 0;
			for (int i = 0; i < n; i++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i - zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int i = 0; i < n - 1; i++) {
				if (map[i][j] == map[i + 1][j]) {
					map[i][j] += map[i + 1][j];
					map[i + 1][j] = 0;
				}
			}
			zerocnt = 0;
			for (int i = 0; i < n; i++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i - zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 1) {
		for (int i = 0; i < n; i++) {
			int zerocnt = 0;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j + zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int j = n - 1; j > 0; j--) {
				if (map[i][j - 1] == map[i][j]) {
					map[i][j] *= 2;
					map[i][j - 1] = 0;
				}
			}
			zerocnt = 0;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j + zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 2) {
		for (int j = 0; j < n; j++) {
			int zerocnt = 0;
			for (int i = n - 1; i >= 0; i--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i + zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int i = n - 1; i > 0; i--) {
				if (map[i][j] == map[i - 1][j]) {
					map[i][j] *= 2;
					map[i - 1][j] = 0;
				}
			}
			zerocnt = 0;
			for (int i = n - 1; i >= 0; i--) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i + zerocnt][j] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	if (dir == 3) {
		for (int i = 0; i < n; i++) {
			int zerocnt = 0;
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j - zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
			for (int j = 0; j < n - 1; j++) {
				if (map[i][j] == map[i][j + 1]) {
					map[i][j] *= 2;
					map[i][j + 1] = 0;
				}
			}
			zerocnt = 0;
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 0) {
					zerocnt++;
				}
				else {
					if (zerocnt != 0) {
						map[i][j - zerocnt] = map[i][j];
						map[i][j] = 0;
					}
				}
			}
		}
	}
	return map;
}


int find_max(vector<vector<int>> map) {
	int maximum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			maximum = max(maximum, map[i][j]);
		}
	}
	return maximum;
}

void solve(int cnt, vector<vector<int>> &map) {
	if (cnt == 5) {
		result = max(find_max(map), result);
		return;
	}
	for (int i = 0; i < 4; i++) {
		vector<vector<int>> tmp = map; //이동시키기 전의 상태를 저장
		map = move(i, map);
		solve(cnt + 1, map);
		map = tmp;   //이동시키기 전의 상태로 복구
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	vector<vector<int>> map;
	vector<vector<int>> tmp;

	cin >> n;

	map.resize(n);
	tmp.resize(n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int num;
			cin >> num;
			map[i].push_back(num);
		}
	}
	solve(0, map);
	cout << result;
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

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

접근 방법

(1) 음수의 가중치가 존재하는 최단 거리 탐색 문제이므로 벨만-포드 알고리즘을 사용하면 된다.

(2) 문제에서 요구하는 출력

    1. 사이클의 가중치 합이 음수인 경우

    2. 버스가 도착지에 도달할 수 없는 경우

    3. 문제 없이 버스가 도착지에 도착한 경우

(3) (2)에서 요구한 조건을 만족하는 경우

   1. 벨만 포드 알고리즘의 핵심은 3중 for문의 가장 바깥 쪽 for문에서 i == N인 순간 갱신이 일어난다면 말할 것도 없         이 사이클의 가중치 합이 음수인 경우이다.

   2.  dist[j] == INF라면 단 한번도 j번째 지점이 갱신이 일어나지 않았다는 것이다. 즉 j번째 지점에 도착할 수 없다라는         말이 된다. 

   3. 만약 1번 조건에서 걸리게 되면 함수가 return이 되므로 1, 2의 조건에 모두 걸리지 않는다면 버스가 문제 없이

      도착하였다는 뜻이 된다.

(4) 주의할 점

 문제에서 주어지는 변수의 범위는 다음과 같다.

 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

 최악의 경우에서 생각해본다면 1번부터 500번 노드까지 거쳐갈 수 있는 최대 노드의 갯수는 499개이고 가중치 C의 최댓값이 10000이므로 499*10000 이므로 INF는 4990000 이상은 잡아줘야 한다.

만약 모든 C가 -10000이면 어떨까? 

for (int i = 1; i <= N; i++) { 
	for (int from = 1; from <= N; from++) {
		for (int j = 0; j < graph[from].size(); j++) {
				//연산 
		}
	}
}

 graph[from].size()가 10 이상 이면 500*500*10*(-10000) = -2,500,000,000 즉 int의 범위를 벗어나 overflow가 발생한다.

그래서 dist는 long long으로 사용해야 적절한 답을 얻을 수 있다.

소스 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 0xFFFFFFF

using namespace std;

vector <pair<int, int>> graph[502];
long long dist[502];
int N, M;

void solve() {

	dist[1] = 0;
	bool updated = false;

	for (int i = 1; i <= N; i++) { 
		updated = false;
		for (int from = 1; from <= N; from++) {
			if (dist[from] == INF) 
				continue;
			for (int j = 0; j < graph[from].size(); j++) {
				int to = graph[from][j].first; 
				int cost = graph[from][j].second;
				if (dist[to] > dist[from] + cost) {
					dist[to] = dist[from] + cost;
					updated = true;
				}
			}
		}
		if (i == N) {
			if (updated == true) { // 1.사이클의 가중치 합이 음수인 경우
				cout << -1 << "\n"; 
				return;
			}
		}
	}
	for (int j = 2; j <= N; j++) {
		if (dist[j] == INF)   // 2. 버스가 도달할 수 없는 경우
			cout << -1 << "\n";
		else 		    // 3. 버스가 잘 도착한 경우
			cout << dist[j] << "\n"; 
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < 502; i++) 
		dist[i] = INF;
	
	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		graph[s].push_back({ e,w });
	}
	solve();
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

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

접근 방법

문자열 검색 알고리즘인 KMP 알고리즘의 구현을 묻는 문제였습니다.

일반적인 문자 Character by Character mapping은 두 문자열의 길이의 곱인 O(NM)만큼 연산을 하게 됩니다.

KMP 알고리즘은 O(N + M)만큼의 시간만에 검색 연산을 해낼 수 있습니다.

KMP 알고리즘은 문자열이 모든 부분 일치하지 않더라도 현재까지 일치했던 영역 내에서의 정보를 최대한 활용합니다.

주로 활용하는 정보는 일치하는 영역 내의 '문자열 내 접두와 접미의 반복'이 있는가? 입니다. 반복이 없으면 일치하는 영역 내에 재검사할 정보가 없기때문에 일치하는 만큼 건너 뛰고, 반복이 있다면 반복하는 영역으로 점프하여 검사하는 것이 기본 아이디어입니다.

아래의 사진을 보면 이해하기 쉽습니다.

KMP 알고리즘은 위와 같이 일치하는 문자열 내에 정보를 최대한 활용함으로써 O(N + M)의 시간복잡도로 문자열 검색을 구현할 수 있습니다.

패턴 문자열 P의 문자열 길이 1 ~ P.length()까지 접두/접미의 길이 k를 미리 계산해놓고 j를 얼마나 이동할지를 결정하는 것이 KMP 알고리즘의 핵심입니다.

ABCABD의 경우,

A, k = 0

AB, k = 0

ABC, k = 0

ABCA, k = 1

ABCAB, k = 2

ABCABD, k = 0 이 되겠습니다.

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
string S, P;

vector<int> get_failure(string p) {
	vector<int> k(p.size(), 0);
	for (int i = 1, j = 0; i < p.size(); ++i) {
		while (j > 0 && p[i] != p[j])
			j = k[j - 1];
		if (p[i] == p[j])
			k[i] = ++j;
	}
	return k;
}

void solve() {
	int cnt = 0;
	vector<int> cd;
	vector<int> k = get_failure(P);
	for (int i = 0, j = 0; i < S.size(); ++i) {
		while (j > 0 && S[i] != P[j])
			j = k[j - 1];
		if (S[i] == P[j]) {
			if (j + 1 == P.size()) {
				++cnt;
				cd.push_back(i - j + 1);
				j = k[j];
			}
			else {
				++j;
			}
		}
	}

	cout << cnt << "\n";
	for (int i = 0; i < cd.size(); ++i) {
		cout << cd[i] << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	getline(cin, S); getline(cin, P);
	solve();
	return 0;
}

개발 환경 : Visual Studio 2019

질문, 덧글, 지적 환영합니다.

문제 링크

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

접근 방법

1. 문제에서 마을은 트리구조로 되어 있다고 얘기하고 있다. 즉 마을의 연결관계를 트리구조로 나타내자.

void dfs(int now, int parent) {
	for (int i = 0; i < adj[now].size(); i++) {
		int there = adj[now][i];
		if (parent != there) {
			tree[now].push_back(there);
			dfs(there, now);
		}
	}
}

DFS를 통해 트리구조를 구현할 수 있다. adj[]는 양 방향으로 인접한 노드에 대한 정보를 담고 있는 벡터이며,

인접한 부분을 탐색을 하되 if (parent != there)라는 조건을 통해 부모 방향으로 접근할 수 없게 자식 방향으로만 탐색하여 트리를 구성하게 된다.

문제에서 제시하는 3가지 조건

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.  
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.  
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다. 

조건 1을 통해 동적계획법을 사용해야 한다는 사실을 깨달을 수 있다. 동적계획법을 하며 메모를 하기 위한 변수로는 

dp[now][in] (in=0 or in=1)을 사용할 것이며 now는 현재노드 번호, in은 현재 마을이 우수마을로 선정되었다면 1 아니면 0을 의미 한다. 

if (include) { //우수 마을이라면
	int ans = 0;
	for(int i = 0; i < tree[now].size(); i++) {
		int next = tree[now][i];
		ans += solve(next, 0);
	}
	return res = ans + cost[now];
}

solve() 함수 내에서 현재 노드가 우수마을로 선정되었을 경우이다. 2번 조건에 따라 다음 마을은 우수마을이 되면 안되므로 자식노드는 우수마을이 되지 않게 (solve(next, include = 0))진입한다. 또한 우수마을로 선정되었을 경우에는 

cost를 더하게 된다.

else { //include == 0
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			int t1 = solve(next, 1);
			int t2 = solve(next, 0);
			ans += max(t1, t2);
		}
		return res = ans;
	}

 이는 현재 노드가 우수마을로 선정되지 않았을 경우이다.

1. 우수마을로 선정되지 않은 경우로 진입을 하게 되는 경우는 이전의 노드가 우수마을이였을 경우가 있다.

2. 우수마을로 선정되지 않은 경우로 진입을 하게 되는 경우는 이전의 노드가 우수마을이 아니였을 경우가 있다.

1의 경우 다음 마을이 우수마을 이던지 아닌지 끝까지 탐색을 해보지 않으면 모른다. 하지만 2의 경우 다음 노드는 무조건 우수마을로 가는것이 이득이기 때문에 max에서 자동으로 우수마을로 가지 않는 값이 걸러질 것이다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 10000

using namespace std;

vector <int> adj[MAX + 1];
vector <int> tree[MAX + 1];
int dp[MAX + 1][2];
int cost[MAX + 1];

void dfs(int now, int parent) {
	for (int i = 0; i < adj[now].size(); i++) {
		int there = adj[now][i];
		if (parent != there) {
			tree[now].push_back(there);
			dfs(there, now);
		}
	}
}

int solve(int now, int include) {
	int &res = dp[now][include];
	if (res != -1) 
		return res;
	if (include) { //우수 마을이라면
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			ans += solve(next, 0);
		}
		return res = ans + cost[now];
	}
	else {
		int ans = 0;
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			int t1 = solve(next, 1);
			int t2 = solve(next, 0);
			ans += max(t1, t2);
		}
		return res = ans;
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &cost[i]);
		dp[i][0] = dp[i][1] = -1;
	}
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 1);
	int result = max(solve(1, 1), solve(1, 0));
	cout << result;
}

개발 환경 : VS2019

질문, 지적 환영합니다!

문제 링크

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

접근 방법

스도쿠의 빈칸을 채우기 위한 조건은 3가지가 있다.

1. 빈칸을 포함하는 행에 1~9까지 숫자가 단 한번씩만 존재해야함

2. 빈칸을 포함하는 열에 1~9까지 숫자가 단 한번씩만 존재해야함

3. 빈칸을 포함하는 정사각형(3X3)에 1~9까지 숫자가 단 한번씩만 존재해야함

(단계 1). 현재 빈칸에 대해 1~9까지 차례대로 위 조건을 검사,

            모든 빈칸이 채워졌다면 단계 4로 이동

(단계 2). 검사 도중 숫자 x가 위의 세 조건을 모두 만족한다면 다음 빈칸으로 이동 후 (단계 1)진행

(단계 3). 현재 빈칸에서 어떤 숫자도 만족 할 수 없다면 전 빈칸으로 이동 후 x+1~9에 대해 (단계 1)진행

(단계 4). 완성된 스도쿠 출력 후 종료

소스 코드

#include <iostream>
#include <vector>
#include <utility>

using namespace std;
vector<pair<int, int>> blank;
int sudoku[9][9] = {0};

void make_sudoku() {
	int num;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> num;
			sudoku[i][j] = num;
			if (num == 0) 
				blank.push_back(make_pair(i, j));
		}
	}
}

int check1(int num, int row) { //행 지정
	for (int i = 0; i < 9; i++) {
		if (sudoku[row][i] == num) { //열 검사
			return 0;
		}
	}
	return 1;
}

int check2(int num, int col) {  //열 지정
	for (int i = 0; i < 9; i++) {
		if (sudoku[i][col] == num) { //열 검사
			return 0;
		}
	}
	return 1;
}

int check3(int num, int row, int col) { // 행,열
	int x = row / 3;
	int y = col / 3;
	x = x * 3;
	y = y * 3;
	for (int i = x; i < x + 3; i++) {
		for (int j = y; j < y + 3; j++) {
			if (sudoku[i][j] == num) { // 3X3박스 검사
				return 0;
			}
		}
	}
	return 1;
}

void solve_sudoku(int cnt) {
	if (cnt == blank.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << sudoku[i][j] << " ";
			}
			cout << "\n";
		}
		exit(0);
	}
	else {
		for (int i = 1; i <= 9; i++) { //빈칸을 채워넣을 숫자
			int x = blank[cnt].first;
			int y = blank[cnt].second;
			if (check1(i, x) * check2(i, y) * check3(i, x, y) == 1) { //조건을 모두 만족할때
				sudoku[x][y] = i;
				solve_sudoku(cnt + 1);
				sudoku[x][y] = 0;
			}
		}
	}
}

int main() {
	make_sudoku();
	solve_sudoku(0);
}

개발 환경 : VS 2019

질문, 지적 환영입니다.

문제 링크

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

접근 방법

 문제에서 요구하는 것을 간단히 정리하자면, A라는 인물과 B라는 인물이 친구 관계를 맺었을 때 A의 친구 수와 B의 친구 수를 더하면 된다. 문제를 읽었을 때 두 집합이 연결(친구 관계) 또는 합(친구의 수)하여 진다는 점에 있어서 유니온 파인드 알고리즘이라는 느낌이 확실히 와 닿는다.

 유니온 파인드는 크게 자신의 루트를 찾는 find함수와, 두 집한간의 연결을 하는 Union함수를 사용한다.

혹여나 두 함수를 이해하지 못했다면 기본적인 UnionFind 알고리즘을 다시 공부하고 풀어보자.

 사실 UnionFind의 구현은 어렵지 않으나, 이 문제는 노드 번호를 이름(문자열)으로 주어지기 때문에 조금 까다롭게 느껴질 수 있다.

1. 문자열을 노드 번호로 정리해 보자

map <string, int> name;

name을 map의 자료형으로 위와 같이 정의했을 때, 아래와 같이 처리할 수 있다.

int idx = 1;
for (int j = 0; j < F; j++) {
	string name1, name2;
	cin >> name1 >> name2;
	if (name.count(name1) == 0) 
		name[name1] = idx++;
	if (name.count(name2) == 0) 
		name[name2] = idx++;
	Union(name[name1], name[name2]);
}

문제를 쉽게 해결하기 위해 이름(문자열)에 대해 번호를 매겨주자. 

 지금까지 입력받은 적이 없는 이름이라면 ( if (name.count(name1)==0) ), 번호를 부여한다( name[name1] = idx++) .

즉 idx는 이름에 대한 번호이며, 입력을 받은적이 있는 이름이라면 이미 번호가 매겨져 있다는 뜻으로 무시해도 된다는 것이다.

 예를 들면

Fred, Bob -> 1, 2

Jason, Bob -> 3, 2

이렇게 처리가 된다. 

이제 어려울 것이 없다. 친구 수는 (cnt[i] = 친구수 (i는 노드 번호) )라는 배열에 저장하며 처리를 할 것이며 Union함수에서 name1과 name2의 친구 관계를 형성함과 동시에 친구수를 더할 것이다.

void Union(int a, int b) {
	a = find(a);
	b = find(b);
	if(a != b)            //이미 친구 관계라면, 친구 수를 합하면 안됨
		cnt[a] += cnt[b]; //친구수의 합
	tree[b] = a;          //친구관계 형성
	cout << cnt[a] << "\n";
}

소스 코드

#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <stdio.h>

using namespace std;
int tree[100010];
int cnt[100010];

int find(int a) { 
	if (tree[a] == -1 || tree[a] == a)  
		return a;
	int root = find(tree[a]);
	return tree[a] = root;
}

void Union(int a, int b) { 
	a = find(a);
	b = find(b);
	if(a != b)              //친구 관계가 아닐 때
		cnt[a] += cnt[b];   //친구 수 합
	tree[b] = a;            //관계를 형성
	cout << cnt[a] << "\n";
}

int main() {

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
	int T , F;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> F;
		map <string, int> name;
		memset(tree, -1, sizeof(tree));
		fill_n(cnt, 100010, 1);
		int idx = 1;
		for (int j = 0; j < F; j++) {
			string name1, name2;
			cin >> name1 >> name2;
			if (name.count(name1) == 0) 
				name[name1] = idx++;
			if (name.count(name2) == 0) 
				name[name2] = idx++;
			Union(name[name1], name[name2]);
		}
	}
}

개발 환경 : VS2019

질문, 지적 환영합니다!