백준 17140번 : 이차원 배열과 연산 - DFS, 시뮬레이션 C++

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

17140번: 이차원 배열과 연산

 

1.문제설명

 

백준 17140번

 

문제에서 R연산과 C연산을 하는 방법을 설명합니다.

초기에 입력으로 주어진 배열로

R연산이나 C연산을 거듭하면서 주어진 조건에 부합하면 종료하면 됩니다.

 

 

---

 

2.접근방법[알고리즘]

 

입력

1 2 3
1 2 1
2 1 3
3 3 3

출력

2

백준 17140번 이차원 배열과 연산 

 

정렬방법

문제에서 주어지는 정렬 방법 대로 조건을 만족할 때 까지

계속 정렬하고 배열에 넣고 정렬하고 배열에 넣고 반복해야합니다.

 

[1, 2 , 3] 정렬 방법은

 

숫자 1 : 1개 {1 : 1}

숫자 2 : 1개 {2 : 1}

숫자 3 : 1개 {3 : 1}

 

문제 조건이 "수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다." 이므로 

{1 : 1} , { 2 : 1 } , { 3 : 1} 순으로 정렬되고 배열에 들어갈 때

1 1 2 1 3 1 이렇게 됩니다.

이 정렬 방법대로 R, C 연산을 계속 반복해야합니다.

 

정렬 구현 코드

for (int i = 1; i <= row; i++) {
    map<int, int> m;

    for (int j = 1; j <= col; j++) {
        if (arr[i][j] != 0) {
            m[arr[i][j]]++;
            arr[i][j] = 0;
        }
    }
    vector<pair<int, int> > v(m.begin(), m.end());

    sort(v.begin(), v.end(), comp);
    int p = 1;

    for (int j = 0; j < v.size(); j++) {
        if (v[j].second == 0 || p>100) break;
        arr[i][p++] = v[j].first;
        arr[i][p++] = v[j].second;
    }
    maxp = max(p - 1, maxp);

}

맵과 벡터를 이용해서

맵으로 숫자 개수를 카운트하고 벡터에 pair 자료형으로 넣어준 뒤

문제 조건대로 정렬을 한 후 정렬 된 상태로 arr에 넣어줬습니다.

 

for문을 돌면서 행이나 열을 돌 때 갯수를 센 후 0으로 초기화 해주어야합니다.

초기화를 해주지 않으면 이전 배열의 숫자가 계속 누적되어 틀립니다.

 

 

---

 

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int arr[202][202], r, c, k, ans = INT_MAX;

bool comp(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.second == b.second) return a.first < b.first;
	else return a.second < b.second;
}

void DFS(int row, int col, int trial) {

	if (trial > 100) {
		return;
	}
	if (arr[r][c] == k) {
		ans = min(ans, trial);
		return;
	}

	if (row >= col) {
		int maxp = 0;
		for (int i = 1; i <= row; i++) {
			map<int, int> m;

			for (int j = 1; j <= col; j++) {
				if (arr[i][j] != 0) {
					m[arr[i][j]]++;
					arr[i][j] = 0;
				}
			}
			vector<pair<int, int> > v(m.begin(), m.end());

			sort(v.begin(), v.end(), comp);
			int p = 1;

			for (int j = 0; j < v.size(); j++) {
				if (v[j].second == 0 || p>100) break;
				arr[i][p++] = v[j].first;
				arr[i][p++] = v[j].second;
			}
			maxp = max(p - 1, maxp);

		}

		DFS(row, maxp, trial + 1);
	}
	else {
		int maxp = 0;
		for (int i = 1; i <= col; i++) {
			map<int, int> m;

			for (int j = 1; j <= row; j++) {
				if (arr[j][i] != 0) {
					m[arr[j][i]]++;
					arr[j][i] = 0;
				}
			}
			vector<pair<int, int> > v(m.begin(), m.end());

			sort(v.begin(), v.end(), comp);
			int p = 1;
			for (int j = 0; j < v.size(); j++) {
				if (v[j].second == 0 || p>100) break;
				arr[p++][i] = v[j].first;
				arr[p++][i] = v[j].second;

			}
			maxp = max(p - 1, maxp);
		}

		DFS(maxp, col, trial + 1);
	}
}


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

	cin >> r >> c >> k;

	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			cin >> arr[i][j];
		}
	}

	DFS(3, 3, 0);

	if (ans == INT_MAX) {
		cout << -1 << '\n';
	}
	else cout << ans << '\n';
	return 0;
}

백준 17140 메모리 및 시간