[백준 BOJ] 21736번 헌내기는 친구가 필요해 (C++/cpp)

문제 설명

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

21736번: 헌내기는 친구가 필요해

 

접근 방법 - 그래프 탐색의 응용문제 (BFS 또는 DFS)

백준의 21736번 문제는 그래프 탐색과 연관된 BFS 또는 DFS를 이용하여 해결해야 하는 문제이다.

해당 문제는, 캠퍼스의 정보가 주어질 때 도연이가 만날 수 있는 사람의 수를 구하여 출력해야 하는 문제이다.

이 문제와 같은 경우엔 둘 중 어느 방법을 써도 되지만, 필자는 큐를 이용한 BFS를 통해 해결을 시도해 보았다.

'I'부터 시작해 상하좌우를 탐색하며 'P'를 찾도록 하는, 기본적인 BFS 방법을 사용하였다.

자세한 설명은 아래에 있으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 캠퍼스의 정보를 저장할 배열(ch)과 방문 여부에 대해 저장할 배열(visit)을 전역 변수로 선언해 둔다.

이때, visit의 배열값은 아래와 같이 의미한다.

- visit의 배열값이 0이라면, 방문하지 않았음(방문 가능)을 의미한다.
- visit의 배열값이 1 또는 그 이상이라면, 방문을 이미 완료하였음(방문 불가능)을 의미한다.

 

2) 캠퍼스의 가로 및 세로(n, m)를 입력받는다.

 

3) BFS 연산에 사용할 큐(q)를 선언해 둔다.

이때, 도연이가 이동하는 공간의 좌표를 해당 큐에 저장할 예정이기 때문에 <int, int> 형식으로 저장할 수 있도록 한다.

 

4) n과 m의 크기만큼, 2중 반복문을 실행하여 ch의 정보를 입력받도록 한다.

여기서 'I'를 입력받았다면, 이는 해당 공간이 탐색의 시작점임을 의미한다.

따라서, 해당 좌표를 q에 즉시 저장하면서 현재 위치의 visit 배열값도 1로 변경한다.

 

5) 도연이가 만난 사람의 수를 저장할 변수 cnt를 0으로 초기화하여 선언한다.

 

6) q가 완전히 빌 때까지, 아래의 연산을 반복한다.

- 변수 2개(i, j)를 선언하고, 이에 각각 현재 탐색 중인 좌표의 행/열 번호를 저장하도록 한다.

- 현재 위치에서 상하좌우를 탐색한다.

만약 특정 방향의 공간의 배열값이 'O' 또는 'P'이고 visit의 값도 0이라면, 이는 해당 공간으로 이동할 수 있음을 의미한다.

따라서 이 경우엔, 해당 visit의 값을 1로 변경하고 위치의 좌표를 q에 저장하도록 한다.

이때 해당 공간의 배열값이 'P'인 경우엔, 어떤 사람을 만났음을 의미하기 때문에 cnt에 1을 더하도록 한다.

- 연산이 한번 끝날 때마다 q에 대하여 pop 연산을 취하고 다음 연산을 수행한다.

 

7) cnt의 값에 따라 출력을 수행하도록 한다.

- 만일 cnt의 값이 0이라면, 사람을 1명도 못 만났음을 의미하기 때문에 "TT"를 출력한다.

- 다만 cnt의 값이 1 이상이라면, 누구라도 만났음을 의미하기 때문에 현재 cnt의 값을 그대로 출력한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <queue>
#include <utility>
#define endl '\n'
using namespace std;

//백준 21736번 코드
char ch[603][603];
int visit[603][603];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	queue<pair<int, int>> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ch[i][j];
			if(ch[i][j]=='I'){
				visit[i][j] = 1;
				q.push(make_pair(i, j));
			}
		}
	}

	int cnt = 0;
	while (!q.empty()) {
		int i = q.front().first;	int j = q.front().second;
		if ((ch[i - 1][j] == 'O' || ch[i - 1][j] == 'P') && visit[i - 1][j] == 0) {
			if (ch[i - 1][j] == 'P') { cnt++; }
			visit[i - 1][j] = 1;
			q.push(make_pair(i - 1, j));
		}
		if ((ch[i + 1][j] == 'O' || ch[i + 1][j] == 'P') && visit[i + 1][j] == 0) {
			if (ch[i + 1][j] == 'P') { cnt++; }
			visit[i + 1][j] = 1;
			q.push(make_pair(i + 1, j));
		}
		if ((ch[i][j - 1] == 'O' || ch[i][j - 1] == 'P') && visit[i][j - 1] == 0) {
			if (ch[i][j - 1] == 'P') { cnt++; }
			visit[i][j - 1] = 1;
			q.push(make_pair(i, j - 1));
		}
		if ((ch[i][j + 1] == 'O' || ch[i][j + 1] == 'P') && visit[i][j + 1] == 0) {
			if (ch[i][j + 1] == 'P') { cnt++; }
			visit[i][j + 1] = 1;
			q.push(make_pair(i, j + 1));
		}
		q.pop();
	}
	if (cnt == 0) { cout << "TT" << endl; }
	else { cout << cnt << endl; }
}

 

제출 결과

(2022.08.11 백준 21736번 문제 제출 결과)