<백준 알고리즘> 3109번 DFS , 그리디 알고리즘

백준 3109번

접근 방법

1. 가장먼저 생각한 것은 bfs나 dfs를 써야할 것 같다는 것 이었다.

2. 문제의 조건에서 파이프끼리 같은 칸에 있으면 안된다는 조건이 있는데 이것이 이미 방문한 곳은 못한다는 의미라고 생각했다.

3. 만약 bfs나 dfs를 쓰려면 3가지 이동경로를 모두 탐색하며 최대 파이프수를 어떻게 만들 수 있을까 생각해봤는데 r이 1인 곳에서 출발할 경우 r이 1인 곳에 도착하고 r이 2인 곳에서 출발할 경우 r이 2인 곳에 도착하는 것처럼 만약 도착지점의 가스관이 방문한 곳이 아니라면 최대한 r이 낮은 곳에 도달할수록 겹치지 않는 경우를 최대로 할 수 있다고 생각했다.

4. 그래서 dfs에서 그리디 알고리즘을 이용하여 가장 r이 작은 곳에서 시작하는 오른쪽 위칸으로 이동을 먼저 고려하고 만약 그 경우에 이동이 안 될 경우 그냥 오른쪽 그 다음 오른쪽 아래로 이동하는 경우를 고려하는 순으로 하며 만약 도착 가스관에 도달한 경우 이미 최선의 선택을 한 후 결과가 나왔으므로 dfs에서 과정에서 추가로 발생하는 다른 경우를 무시하고 그냥 반환을 해준다.

5.출발 지점은 첫번째 열의 모든 좌표에 대해서 진행한다.

코드 설명

	for (int i = 1; i <= R; i++)
	{
		isReached = false;
		dfs(i, 1);
	}

dfs를 할 때 근처빵집 가스관 == 첫 번째 열에 대해서 모두 진행해준다. isReached를 통해 출발 좌표에서 도착 가스관에 도달하면 true로 바꿔서 다른 경우를 무시하고 반환하도록 한다.(이미 최선의 선택을 한 것 이기에)

void dfs(int y,int x)
{

	if (y < 1 || x < 1 || y > R || x > C || isVisited[y][x] == 1 || board[y][x] == 'x')
		return;

	if (isReached == true)
	{
		return; //이미 도달했으면 계속해서 반환
	}
	
	if (x == C)
	{
		ans++;//처음 도달할 경우
		isReached = true;

		return;
	}

	

	isVisited[y][x] = 1;

	for (int i = 0; i < 3; i++)
	{
		dfs(y + dyy[i], x + dxx[i]); 
	}

	
}

이동 순서는 오른쪽 위 -> 오른쪽 ->오른쪽 아래로 진행하여 최대한 겹치는 경우가 없게한다.

전체 코드

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <deque>



using namespace std;

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

int dxx[3] = { 1,1,1 };
int dyy[3] = { -1, 0, 1 };



int isVisited[10001][501] = {0};

char board[10001][501] = {};

int R,C;

int ans = 0;

bool isReached = false;

void dfs(int y,int x)
{

	if (y < 1 || x < 1 || y > R || x > C || isVisited[y][x] == 1 || board[y][x] == 'x')
		return;

	if (isReached == true)
	{
		return;
	}
	
	if (x == C)
	{
		ans++;
		isReached = true;

		return;
	}

	

	isVisited[y][x] = 1;

	for (int i = 0; i < 3; i++)
	{
		dfs(y + dyy[i], x + dxx[i]);
	}

	
}

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

	cin >> R>>C;

	for (int i = 1; i <= R; i++)
	{
		
		for (int j = 1; j <= C; j++)
		{
			cin >> board[i][j];
		}
	}

	for (int i = 1; i <= R; i++)
	{
		isReached = false;
		dfs(i, 1);
	}


	cout << ans;

	return 0;
}