뚝딱뚝딱

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

토마토 2차원 배열 입력 문제 풀이 참고

2024.01.22 - [CO-TE/백준] - [백준] 7576번 C++ "토마토" 풀이 / BFS, 너비우선탐색

💡 토마토(3차원 배열 입력 ver.)

✅ 문제 풀이

• 이전에 풀었던 토마토 (7576번) 문제와 풀이 방식은 동일한데, 입력으로 주어지는 차원이 3차원으로 늘어나 높이까지 고려해야 한다.
• 따라서 입력을 받는 arr 벡터도 3차원으로 정의해주었고, 좌표를 담는 queue의 자료형도 pair를 한번 더 감싸서 3개의 int 쌍을 갖도록 하였다.
  => pair<pair<int,int>,int>
• 입력으로는 한 판 씩 맨 아래 층 부터 들어오기 때문에 for문의 시작에 for문을 하나 더 추가해서 높이마다 한판 씩 정보를 입력 받도록 하였다.
  = 마지막에 확인할 때도 맨앞에 높이에 대한 for문만 추가해주었다.
•  queue에 push할때도 queue의 자료형에 맞게 두 개의 pair 쌍으로 값을 입력해주었다. 여기서 x 와 y 는 전체 pair에서도 첫번째인 pair 쌍에 해당하기 때문에 front().first.first, front().first.second 로 두번씩 들어가 접근하도록 하였고, z는 전체 pair에서 두번째 값이기 때문에 front().second로 접근하도록 하였다.
• 높이에 대한 조건이 추가되면서, 인접한 범위가 위, 아래 까지 늘어났다. 따라서 총 6번의 탐색을 해야하므로, bfs 함수내에서 사용하는 dx, dy를 수정해주었다. 맨뒤에 높이에 대한 변화가 없도록 {0,0}을 추가해준다. 그리고 높이에 대한 dz를 추가해주고, {0,0,0,0,-1,1} 으로 높이에 대해서만 변화가 있도록 한다.
• bfs 함수 내에서 탐색은 4->6으로 수정해주고, 함수의 인자로는 x,y 뿐만 아니라, z도 받도록 하여, 전체 위치를 표시해준다.
• arr의 인덱스 범위에서도 z는 0이상 h이하에 있도록 검사한다.
• 나머지 로직은 동일하다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, m, h;
vector<vector<vector<int>>> arr;
queue<pair<pair<int, int>,int>> q;
queue<pair<pair<int, int>,int>> temp;

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

int answer = 0;

void bfs(int x, int y, int z) {
	for (int i = 0; i < 6; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		int nz = z + dz[i];

		if (nx >= 0 && nx < n&&ny >= 0 && ny < m&& nz>=0 && nz< h&& arr[nx][ny][nz] == 0) {
			arr[nx][ny][nz] = 1;
			temp.push(pair<pair<int, int>, int> (pair<int, int>(nx, ny),nz));
		}
	}
}

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

	cin >> m >> n >> h;

	arr.resize(n, vector<vector<int>>(m, vector<int> (h)));

	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> arr[i][j][k];
				if (arr[i][j][k] == 1) {
					q.push(pair<pair<int, int>, int> (pair<int, int> (i, j), k));
				}
			}
		}
	}

	while (!q.empty()) {
		bfs(q.front().first.first, q.front().first.second, q.front().second);
		q.pop();
		if (q.empty()) {//한번 돌았음을 의미
			answer++;
			while (!temp.empty()) {
				q.push(pair<pair<int, int>, int> (pair<int, int> (temp.front().first.first, temp.front().first.second),temp.front().second));
				temp.pop();
			}
		}
	}

	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j][k] == 0) {
					cout << -1;
					return 0;
				}
			}
		}
	}

	cout << answer - 1;

	return 0;
}

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

💡 적록색약

✅ 문제 풀이

• 골드 치고 쉬운 dfs 문제
• 보자마자 어떻게 풀어야 할지 접근방식이 바로 보이는 문제!!
• 주의해야 할 점은 적록색약일 경우 R,G가 인접해있으면 같은 영역으로 본다는 점
• 이런 영역 문제를 풀 때는 방문한 칸에 대해서는 방문 표시를 하기때문에, 두 가지 접근 방식에 대해서 서로 영향을 받지 않기 위해서 arr를 두개를 만들고 시작했다.
• arr1은 적록색약이 아닌 사람이 보는 영역으로, R은 1, G는2, B는3 을 저장했다.
• arr2는 적록색약인 사람이 보는 영역으로, R과 G는 1, B는 3을 저장했다. 이게 핵심이다. R과 G를 같은 값으로 배정하여 같은 영역으로 인식되도록 하였다.
• 방문한 것에 대해서는 arr 값을 0으로 갱신하도록 하며, 방문 여부를 체크했다.
• arr 크기만큼 순회하면서 각 칸이 0이 아니면 dfs 함수를 호출하여, 현재 위치와 현재 위치의 값, 그리고 참조할 arr를 인자로 넘겨주었다.
• arr1과 arr2에 대해서 각각 취해야 하기 때문에 두번 씩 호출해 주었다.

• dfs 함수 내 동작
• 현재 칸을 방문했으므로 값을 0으로 갱신해준다.
• 현재 칸을 기준으로 상하좌우가 arr의 범위내에 있고, 현재 칸과 값이 동일하면 같은 영역이므로 해당 칸에 대해서 DFS를 재귀호출하여 한 영역에 대해 계속 탐색하도록 하였다.

• 다시 돌아와서, main의 2중 for문에서 dfs가 호출되었다는 것은 영역의 시작과 같은 의미이므로, dfs를 호출한 후에는 answer을 증가시켜 영역을 개수를 카운트 하였다.
• 이때 적록색약이 아닌 경우는 answer1을, 적록색약인 경우는 answer2를 카운트 하도록 하였다.
• 최종 answer들을 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int n;
vector<vector<int>> arr1;
vector<vector<int>> arr2;

int answer1 = 0;
int answer2 = 0;

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

void dfs(int i, int j, int num, vector<vector<int>> &arr) {
	arr[i][j] = 0;
	
	for (int k = 0; k < 4; k++) {
		int x = i + dx[k];
		int y = j + dy[k];
		if (x >= 0 && x < n&&y >= 0 && y < n&&arr[x][y] == num) {
			dfs(x, y, num, arr);
		}
	}
}

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

	cin >> n;

	arr1.resize(n, vector<int>(n));
	arr2.resize(n, vector<int>(n));

	string str;
	for (int i = 0; i < n; i++) {
		cin >> str;
		for (int j = 0; j < n; j++) {
			if (str[j] == 'R') {
				arr1[i][j] = 1;
				arr2[i][j] = 1;
			}
			else if (str[j] == 'G') {
				arr1[i][j] = 2;
				arr2[i][j] = 1;
			}
			else {
				arr1[i][j] = 3;
				arr2[i][j] = 3;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr1[i][j] != 0) {
				dfs(i, j, arr1[i][j], arr1);
				answer1++;
			}
			if (arr2[i][j] != 0) {
				dfs(i, j, arr2[i][j], arr2);
				answer2++;
			}
		}
	}
	
	cout << answer1 << " " << answer2;

	return 0;
}

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

💡 토마토

✅ 문제 풀이

• BFS를 활용하는 문제이다.
• queue를 사용하여 방문해야 할 곳을 pair<int,int> 형태의 좌표를 저장하도록 하였다.
• 먼저 토마토에 대한 2차원 배열을 순회하면서 값이 1이면 그 위치를 q라는 queue에 pair<int,int> 형태로 넣는다.
• 모두 탐색한 후에는 while문으로 q가 빌때까지 bfs를 수행한다.
• q에서 가장 앞에 있는 front의 first와, second를 bfs의 인자로 넘겨준다.

• BFS함수의 동작
  1. 인자로 받은 위치를 가지고, 동 서 남 북 방향에 있는 값이 배열의 인덱스 범위에 유효하며, 값이 0인지 확인한다.
  2. 위의 조건을 만족한다면 해당 위치의 arr값을 1로 변경해주고, temp라는 이름의 queue에 해당 위치를 pair<int,int> 형태로 넣어준다.

• BFS함수를 돌고 나면 q에서 pop한다.
• 그런다음, 현재 q가 비어있다면, 하루에 익을 수 있는 토마토는 다 익은 것이므로 하루를 카운트 하기 위해 answer를 1 증가시킨다.
• 새로 익어진 토마토에 대한 정보를 가진 temp 있는 위치 정보들을 q에 다 옮겨놓는다.
• 그리고나서 이어지는 다음 while문 동작부터는 다음 날짜에 대한 동작을 진행하는 것이다.
• 그런데, q가 비어지게 되면 temp가 비어있고, 그날이 마지막 날이었더라도 하루가 무조건 더해지게 되기 때문에, 마지막에는 answer에서 1을 뺀 값이 답이된다.
• while문을 모두 수행하고 나면, 갱신된 2차원 배열을 순회하면서, 하나라도 0이 있는 값이 있는지 찾아본다.
• 이는 0이 하나라도 있다면 모든 토마토가 익어질 수 없다는 뜻이므로 -1을 출력하고 프로그램을 종료하기 위함이다.
• 그렇지 않다면 answer-1을 출력하도록 하여, 토마토 판에서 토마토가 다 익는데 걸리는 날을 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, m;
vector<vector<int>> arr;
queue<pair<int, int>> q;
queue<pair<int, int>> temp;

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

void bfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&arr[nx][ny] == 0) {
			arr[nx][ny] = 1;
			temp.push(pair<int, int>(nx, ny));
		}
	}
}

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

	cin >> m >> n;

	arr.resize(n,vector<int>(m));

	bool end = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				q.push(pair<int,int>(i, j));
			}
		}
	}

	while (!q.empty()) {
		bfs(q.front().first, q.front().second);
		q.pop();
		if (q.empty()) {//한번 돌았음을 의미
			answer++;
			while(!temp.empty()) {
				q.push(pair<int,int>(temp.front().first, temp.front().second));
				temp.pop();
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				cout << -1;
				return 0;
			}
		}
	}

	cout << answer-1;

	return 0;
}

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

💡 DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

[입력]
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

[출력]
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

✅ 문제 풀이

• DFS와 BFS의 로직을 나누어서 두번의 결과를 따로 구하고 출력하도록 하였다.
• 일단 입력으로 받은 간선의 정보를 2차원 벡터에 저장하였다.
  이때 양방향 간선이라는 점을 고려하여, A->B로 B->A로의 간선 정보를 저장해준다.
• S노드에서 시작하므로, S번의 visited를 true로 설정하고 시작한다.
• 간선 정보를 담은 arr배열을, 각 노드에 대해서 오름차순 정렬해준다. 노드 번호가 낮은 것부터 방문해야 하기 때문이다.
• dfs함수는, arr배열의 s번 vector를 탐색하는데, 먼저 방문하는 노드를 시작으로 또 dfs를 재귀호출하며 방문하도록 한다. 
• bfs함수는, arr배열의 s번 vector를 탐색하는데, 각 노드를 탐색할 때마다 queue에 담아주고, 해당 벡터를 다 탐색하고 나서는 queue의 front부터 탐색하며 bfs를 재귀호출하도록 한다.
• 각각의 결과는 dfs_result, bfs_result에 담은 후 출력한다.

✏ 코드 전문

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

using namespace std;

void dfs(int s, vector<vector<int>> arr, vector<bool> &visited, vector<int> &dfs_result) {
	for (int i = 0; i < arr[s].size(); i++) {
		if (!visited[arr[s][i]]) {
			visited[arr[s][i]] = true;//방문
			dfs_result.push_back(arr[s][i]);
			dfs(arr[s][i], arr, visited, dfs_result);
		}
	}
}
void bfs(int S, vector<vector<int>> arr, vector<bool> &visited, vector<int> &bfs_result, queue<int> &q) {
	for (int i = 0; i < arr[S].size(); i++) {
		if (!visited[arr[S][i]]) {
			visited[arr[S][i]] = true;//방문
			q.push(arr[S][i]);
			bfs_result.push_back(arr[S][i]);
		}
	}
	while (!q.empty()) {
		int next = q.front();
		q.pop();
		bfs(next, arr, visited, bfs_result, q);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, S;
	cin >> N >> M >> S;

	vector<vector<int>> arr(N+1);
	vector<bool> visited1(N + 1, false);//dfs에서사용
	vector<bool> visited2(N + 1, false);//bfs에서사용
	queue<int> q;//bfs에서 사용
	vector<int> dfs_result;
	vector<int> bfs_result;
	for (int i = 0; i < M; i++) {//간선 정보 입력받기
		int n1, n2;
		cin >> n1 >> n2;

		arr[n1].push_back(n2);
		arr[n2].push_back(n1);
	}

	for (int i = 1; i < N + 1; i++) {//노드별로 간선 정보를 오름차순 정렬
		sort(arr[i].begin(), arr[i].end());
	}


	visited1[S] = true;
	visited2[S] = true;
	dfs_result.push_back(S);
	bfs_result.push_back(S);

	dfs(S, arr, visited1, dfs_result);
	bfs(S, arr, visited2, bfs_result, q);

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

DFS/BFS 알고리즘의 대표적인 문제 "타겟 넘버"의 풀이방법이다.

그 전에 DFS/BFS의 개념을 정리하자면,

그래프와 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘이다.

문제에 따라서 각각의 접근방식을 달리 사용할 수 있다.

💡 DFS (깊이 우선 탐색)

• 깊이 우선 탐색은 한 분기를 끝까지 탐색한 후 다음 분기로 넘어가는 방식의 탐색 알고리즘이다.
• 시작 노드에서 출발하여 가능한 한 깊이 들어가면서 탐색한다.
• 주로 재귀 함수를 사용하여 구현하거나 스택(Stack)을 이용한다.
• 특정 경로를 탐색하다가 더 이상 진행할 수 없는 상황에 도달하면 이전 단계로 돌아와 다른 경로를 탐색한다.
• DFS는 그래프에서 사이클을 찾거나 깊이에 관한 문제를 해결하는 데 유용하다.

예시) 미로를 탐색할 때 한 방향으로 직진하다가 막히면 되돌아가서 다른 방향으로 계속 진행하는 방식이다.

💡 BFS (너비 우선 탐색)

• 너비 우선 탐색은 시작 노드에서부터 가까운 노드부터 차례대로 탐색하는 방식의 탐색 알고리즘이다.
• 큐(Queue) 자료 구조를 사용하여 구현한다.
• 주로 최단 경로를 찾는 문제에 사용되며, 모든 가까운 노드를 우선 탐색하여 최단 경로를 찾아낸다.
• BFS는 그래프에서 사이클을 찾지 않고, 가까운 노드를 먼저 탐색하는 데 적합하다.

예시) 같은 미로에서 모든 가로행을 먼저 탐색하고, 그 다음에 세로열을 탐색하는 방식이다.

결론적으로

DFS는 깊이 관련 문제를 해결할 때 유용하며, BFS는 최단 경로와 가까운 노드를 탐색할 때 효과적이다.

그럼 다시 본론으로 돌아와서...

해당 타겟 넘버 문제를 살펴보자. 

문제에서는 주어지는 숫자 배열 numbers를 각각 더하거나 빼면서 target 값을 생성하는 방법을 반환하는 solution을 찾도록 되어있다.

그렇다면 numbers에 있는 숫자 개수 만큼 + 또는 -의 연산자가 필요하다.

모든 숫자 앞에는 + 또는 -의 연산을 해야하므로, 각각의 숫자는 + 또는 - 중에 선택되어야 하며, 트리 형태로 표현해보면 다음과 같이 표현할 수 있다.

즉, 모든 경우의 수에 대해서 끝까지 탐색해 봐야 target 값이 도출되는지를 확인할 수 있다.

따라서 위 문제는 DFS로 해결할 수 있다.

DFS는 재귀 함수를 이용한다. 그럼 재귀함수를 어떻게 구성할 수 있을까?

한번의 연산에서는 +연산을 했을 때와 -연산을 했을 때의 두가지 경우를 고려할 수 있기 때문에, 두 연산을 각각 수행할 수 있도록 재귀함수를 사용해야 한다.

그런데, 마지막 노드에 대해서는 더이상 탐색할 것이 없기 때문에=해당 분기에 대해서는 다 탐색을 했기 때문에, 해당 연산이 target이 나오는지를 확인하고, 해당하면 이 분기는 타켓 넘버를 계산할 수 있는 경우의 수중 하나가 되기 때문에 1을 반환하도록 할 것이다.

따라서 solution이 시작될 때는 vector가 비어있는지부터 확인하여(비어있다면 다 탐색했다는 의미이므로), 비어있으면 return하는 동작을 수행하도록 한다.

그렇지 않다면 vector의 마지막 요소를 따로 저장해둔뒤, 해당 요소를 삭제한다.

그리고 solution함수를 호출해서 마지막 요속 삭제된 vector를 넘겨주고, target에 마지막 요소를 더한 값을 target자리로 같이 넘겨준다. 반환된 값을 answer에 저장되도록 한다.

이를 빼기 연산에 대해서도 동일하게 수행한다.

target에 vector의 마지막 요소를 더하거나 뺌으로써 탐색을 마쳤을 때 최종 target값이 0이 되면 해당 분기는 하나의 경우의 수가 되는 방식으로 생각했다. (=수학을 잘하자..)

그러면 최종적으로 answer에는 모든 경로를 탐색하여 얻은 "타겟 넘버를 만드는 경우의 수"를 저장하게 될 것이다.

코드는 아래와 같다.

int solution(vector<int> numbers, int target) {
    if(numbers.empty()){
        if(target==0) return 1;
        else return 0;
    }
    
    int answer = 0;
    int top = numbers.back();
    numbers.pop_back();
    
    answer+=solution(numbers, target+top);
    answer+=solution(numbers, target-top);
    
    return answer;
}