BOJ 21736 - 헌내기는 친구가 필요해(DFS,BFS)

자력으로 풀어서 두번째로 잘 풀고 성장했다는 느낌을 받은 문제에 대해서 정리해 본다. 

DFS, BFS 개념에 대해서 1,2주 전만 해도 명확하게 잡히지 않고 구현할때 헤매는 느낌이 있었는데 오늘 문제를 풀면서

어느정도 감을 잡은것 같은 느낌을 받았기에 정리함.

 

문제번호

21736 - 헌내기는 친구가 필요해

 

문제 설계

1. 시작점 I에서 출발하여야 하므로 I에 대한 정보를 x,y변수에 처음 저장 (시작점 정보)

 

2. 격자 탐색 + 연결된 영역을 순회해 X ( dx, dy로 관리하여 다음번 순회 처리)

(벽)을 제외한 모든 영역을 탐색하며 P의 개수를 카운트

 

3. 방문 관리를 visited 변수를 따로 두어 classic 하게 해결함 (방문 처리)

BFS/DFS 중 하나로 전체 도달 가능한 영역을 탐색

 

생각한 문제 패턴

2차원 격자 탐색 -> 상하좌우 이동 -> 방문 체크 필요.

벽이 존재하고 한 시작점에서 퍼져나가는 구조라

BFS 혹은 DFS 패턴.

최단거리는 요구하지 않으므로 단순 탐색 문제로 판단.

 

알고리즘

시작점 I를 찾은 뒤 DFS, BFS 수행.

DFS의 경우  stack 재귀 처리

BFS 는 queue에 좌표를 저장하기 위해 pair로 저장

push 시점에 visited 처리.

 

공통적으로 탐색 중 P를 만나면 카운트 증가.

 

성장한 부분

시작점, 다음번 노드 이동, 방문 처리의 구조를 파악하여 문제를 설계함 

BFS에서 pop 위치의 논리를 재구성해봄 

처음 방문 시점 = 처리 시점” 개념을 이해함.

방문 관리 타이밍과 탐색 흐름을 의식적으로 설계함.

 

개선할 점, 추가 탐구할 점 

BFS에서 q.front()를 반복 호출하는 대신 cur 변수로 분리하면 가독성 향상.

거리 정보가 필요한 문제로 확장 가능 -> 다익스트라 (dist 배열 추가 연습 필요).

DFS/BFS를 각 상황에 맞게 최적으로 선택하는 기준을 더 명확히 정리할 것.

(미로탐색, 최단거리, 가중치 간선 etc)

 

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

using namespace std;

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

void dfs(vector<vector<char>> &array, vector<vector<bool>> &visited,  int startx, int starty, int &cnt)
{
	visited[startx][starty] = true;

	for(int i=0; i<4; i++)
	{
		int x = startx + dx[i];
		int y = starty + dy[i];

		if(x<0 || x>=array.size() || y<0 || y>=array[0].size()) continue;
		
		if(visited[x][y] == false && array[x][y] != 'X' )
		{

			if(array[x][y] == 'P') 
			{
				cnt++;
			}
			dfs(array,visited,x,y,cnt);
		}
		
	}
}

void bfs(vector<vector<char>> &array, vector<vector<bool>> &visited, int startx, int starty, int &cnt)
{
	queue<pair<int,int>> q;
	visited[startx][starty] = true;

	q.push({startx,starty});
	
	while(!q.empty())
	{
		for(int i=0; i<4; i++)
		{
			int x = q.front().first + dx[i];
			int y = q.front().second + dy[i];
	

			if(x<0 || x>=array.size() || y<0 || y>=array[0].size()) continue;

			if(visited[x][y] == false && array[x][y] != 'X')
			{
				if(array[x][y] == 'P')
				{
					cnt++;
				}
				visited[x][y] = true;
				q.push({x,y});

			}
		}
		//4방향 다 검사한다음 front 정보 다 쓰고 나서 최종적으로 pop
		q.pop();
	}
	
}

int main() {
	int n, m;
	cin>>n>>m;
	vector<vector<char>> array(n,vector<char>(m));
	vector<vector<bool>> visited(n,vector<bool>(m, false));

	int startx;
	int starty;

	for(int i=0; i<n; i++)
	{
		string input;
		cin>>input;

		for(int j=0; j<m; j++)
		{
			array[i][j] = input[j];
			if(array[i][j] == 'I')
			{
				startx = i;
				starty = j;
			}
		}
	}

	int cnt =0;

	bfs(array, visited, startx, starty, cnt);

	if(cnt >0) cout<<cnt;
	else if(cnt ==0) cout<<"TT";

}