BOJ 3109 - 빵집

3109번: 빵집 (acmicpc.net)

 

접근방법

이번 문제는 그래프 탐색을 통해 오른쪽, 오른쪽 대각 위, 오른쪽 대각 아래 이렇게 총 3가지로 이동하며 마지막 열에 도달하는 문제이다.

이 과정에서 발생하는 문제는 다음과 같다.

 

1. 어떻게 하야 가장 많은 파이프가 지나갈 수 있도록 배치할 수 있을까?

2. 도착점까지 연결하는 파이프는  하나여야 한다.

 

먼저 1번부터 해결해보자.

예제 1번을 보자

 

5 5
.xx..
..x..
.....
...x.
...x.

 

여기서 0,0 에서 출발한 파이프 라인은 최대한 위쪽을 붙어서 이동해야 한다.

 

5 5
1xx.1
.1x1.
..1..
...x.
...x.

이런게 1의 경로를 따라 이동해야 하므로, 움직이는 순서는 -1, 0 ,1 이어야 한다. (중요)

 

이제 2번째 문제인 "도착점까지 연결하는 파이프는  하나여야 한다." 를 보자.

만약 마지막 열에 도착하여 경로가 완성되었으면 그 나머지는 dfs를 할 필요가 없다.

따라서, 연결 성공시 그 즉시 dfs종료하도록 설정해야 한다.

 

이를 어떻게 해결할 수 있을지 생각해보았는데 정말 답이 없어서 참고했다.

bool dfs() {
	
    if(y == c-1)
        return true;

    // 생략
    for(int i=0;i<3;i++){
        if(dfs(x,y)) {
            return true;
        }	
    }
    return false;
}

y == c-1 이면 경로를 찾았다는 뜻으로 그 즉시 종료할 필요가 있다.

따라서, if(dfs(x,y))  return true; 를 통해 호출된 재귀함수에게도 알려 그 즉시 함수가 끝나도록 설정할 수 있다.

 

 

 

코드

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

#define ll long long

using namespace std;

// r = x
int xPos[] = { -1,0,1 };
int yPos[] = { 1,1,1 };

int r, c;
char map[10001][10003];
bool visited[10001][10003];
vector<pair<int,int>> start;
int sum;
int res;

/*
arr : 1 1 1 0 2
v : 3 , 1 (3원 개수, 2원 갯수)

*/
int cnt = 0;

void print() {
	cout << endl;
	for (int i = 0; i < c; i++) {
		for (int j = 0; j < r; j++) {
			cout << visited[i][j] << ' ';
		}
		cout << endl;
	}
}

bool dfs(int x, int y) {
	if (y == c - 1 && !visited[x][y]) {
		visited[x][y] = true;
		cnt++;
		//print();
		return true;
	}

	visited[x][y] = true;

	for (int i = 0; i < 3; i++) {
		int curX = x + xPos[i];
		int curY = y + yPos[i];
		


		if (curX < 0 || curY < 0 || curX >= r || curY >= c)	continue;
		if (visited[curX][curY] || map[curX][curY] == 'x') continue;
		if (map[curX][curY] != '.')	continue;

		//cout << curY << ", " << curX << endl;
		if (dfs(curX, curY))
			return true;
		/* 이거하면 뚝 끊김
		else
			return false;*/
	}
	return false;
}
int main() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
			
		}
	}

	for (int i = 0; i < r; i++) {
		visited[i][0] = true;
		//cout << "start: " << i << " , " << 0 << endl;
		dfs(i, 0);
		
	}
	cout << cnt;
}