[알고리즘] DFS/BFS 활용 ③

양현지·2024년 4월 8일

1. 개요

1) 문제 개요

N행M열의 보드판에 ①빨간 구슬, ②파란 구슬, ③구멍, ④장애물(벽)이 존재한다.
①빨간 구슬 : 구멍을 통해 빠져나가야하며,
②파란 구슬 : 구멍을 통해 빠져나가서는 안된다.
보드판은 상하좌우 기울임을 통해 구슬을 움직일 수 있다. 이때 장애물(벽)과 구멍은 변함이 없다.

10번 이내 빨간 구슬을 구멍 밖으로 빼낼 수 있다면, 이를 위해 기울인 횟수를 반환 OR -1을 반환하도록 한다.

2) 입출력 예시

ⓐ 입력

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

ⓑ 출력

각 화살표가 한 번의 기울임을 의미
총 5번의 기울임 끝에 빨간 구슬이 O(구멍)을 통과

※ 기존의 DFS/BFS 문제와의 차이는 한번의 움직임에 한칸씩 움직이는 것이 아닌 '벽'이 나올때까지 구슬이 움직인다는 점이다. 또한 빨간 구슬과 파란 구슬을 모두 추적해야만 문제의 조건(파란 구슬은 구멍을 통과하지 않은 상태에서, 빨간 구슬만이 구멍을 통과)을 만족하는 상태를 얻을 수 있다.

2. Solution I.

빨간 구슬과 파란 구슬을 동시에 추적해야하지만 우선 파란 구슬을 신경 쓰지 않고 알고리즘을 구현해보도록 한다.

1) 코드 예시

#include <iostream>
#include <vector>
using namespace std;

/*
N행M열
- 빨간 구슬 out, 파란 구슬은 빠지면 안됨
- 상하좌우 기울이기 가능
*/
int N, M;
vector<vector<char>> mp;
vector<vector<bool>> v;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int res = 11;
int x, y;

void dfs(int i, int j, int cnt)
{
	// 경로 표시 (디버깅을 위해 *)
	cout << "(" << i << "," << j << ")" << endl;
	for (int k = 0;k < 4;k++)
	{
		if (dx[k] + i < 0 || dx[k] + i >= M || dy[k] + j < 0 || dy[k] + j >= N)
			continue;
		if (mp[dx[k] + i][dy[k] + j] == 'O')
		{
			if (cnt < res)
				res = cnt;
			break;
		}
		if (mp[dx[k] + i][dy[k] + j] != '.')
			continue;
		if (v[dx[k] + i][dy[k] + j] == true)
			continue;

		int a = dx[k] + i;
		int b = dy[k] + j;
		v[a][b] = true;
		while (1)
		{
			if (a + dx[k] < 0 || a + dx[k] >= N || b + dy[k] < 0 || b + dy[k] >= M)
				break;
			if (mp[a + dx[k]][b + dy[k]] == 'O')
			{
				if (cnt < res)
					res = cnt;
				break;
			}
			if (mp[a + dx[k]][b + dy[k]] != '.')
				break;
			a += dx[k];
			b += dy[k];
			v[a][b] = true;
		}
		dfs(a, b, ++cnt);
	}
}

int main()
{
	cin >> N >> M;
	int rx, ry, bx, by;
	v = vector<vector<bool>> (N, vector<bool>(M, false));
	for (int i = 0;i < N;i++)
	{
		vector<char>line;
		for (int j = 0;j < M;j++)
		{
			char tmp;
			cin >> tmp;
            // 구슬과 구멍의 위치
			if(tmp == 'O') { x = i; y = j;}
			if(tmp == 'R') { rx = i; ry = j;}
			if(tmp == 'B') { bx = i; by = j;}
			line.push_back(tmp);
		}
		mp.push_back(line);
	}
	v[rx][ry] = true;
	dfs(rx, ry, 1);

	if (res != 11)
		cout << res << endl;
	else
		cout << "-1" << endl;
	
	return 0;
}

위 코드대로 실행 시 아래의 예제를 만족하지 않는다.

경로를 출력해본 결과 다음과 같다.
(1,1) -> (2,1) -> (2,3) -> (1,3) -> (1,5) -> (4,5) -> (4,6) -> (4,1) -> (7,1)
총 8번의 움직임으로 계산을 한다. 그런데 (4,5) -> (4,6)은 최단 경로에 포함되지 않으므로 결과값은 7번이 나와야한다.

2) 수정된 코드

#include <iostream>
#include <vector>
using namespace std;

#define MAX 11

int n, m;
vector<vector<char>> mp;
vector<vector<bool>> v;

int res = MAX;

struct pos
{
    int xpos;
    int ypos;
};

pos rpos, bpos, hpos;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void dfs(pos rPos, pos bPos,int cnt)
{
    cout << "(" << rPos.xpos<< "," << rPos.ypos << ") cnt : "<<cnt<< endl;
    if (rPos.xpos == hpos.xpos && rPos.ypos == hpos.ypos)
    {
        res = min(cnt, res);
        // return; => return 하면 완전 탐색으로 결과값을 찾으면 바로 함수 종료하므로, 최소값을 찾을 수 없음
    }
    if (cnt > 10) return;
    // 상하좌우 탐색
    for (int k = 0;k < 4;k++)
    {
        int nx = rPos.xpos + dx[k];
        int ny = rPos.ypos + dy[k];
        // 1. 가장자리를 넘어간 경우
        if (nx <= 0 || ny <= 0 || nx >= n-1 || ny >= m-1) continue;
        // 2. 장애물인 경우
        if (mp[nx][ny] == '#' || mp[nx][ny]=='B') continue;
        // 3. 이미 방문한 경우
        if (v[nx][ny]) continue;
        
        if (nx == hpos.xpos && ny == hpos.ypos)
        {
            res = min(res, cnt);
            return;
        }

        // 벽에 닿을 때까지 이동
        int a=nx, b=ny;
        v[a][b] = true;
        while (1)
        {
            if (a+dx[k] <= 0 || b+dy[k] <= 0 || a+dx[k] >= n - 1 || b+dy[k] >= m - 1) break;
            if (a + dx[k] == hpos.xpos && b + dy[k] == hpos.ypos)
            {
                res = min(res, ++cnt);
                return;
            }
            if (mp[a + dx[k]][b + dy[k]] != '.') break;
            if (v[a + dx[k]][b + dy[k]]) break;
            a += dx[k];
            b += dy[k];
            v[a][b] = true;
        }
        pos rNewPos;
        rNewPos.xpos = a; rNewPos.ypos = b;
        pos bNewPos;
        bNewPos.xpos = a; bNewPos.ypos = b;
        dfs(rNewPos, bNewPos, cnt+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    mp = vector<vector<char>>(n, vector<char>(m, 0));
    v = vector<vector<bool>>(n, vector<bool>(m, false));

    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < m;j++)
        {
            char tmp;
            cin >> tmp;

            mp[i][j] = tmp;
            if (tmp == 'R') { rpos.xpos = i;rpos.ypos = j; }
            if (tmp == 'B') { bpos.xpos = i;bpos.ypos = j; }
            if (tmp == 'O') { hpos.xpos = i;hpos.ypos = j; }
        }
    }
    v[rpos.xpos][rpos.ypos] = true;
    dfs(rpos,bpos, 0);
    
    if (res == 11) cout << "-1"<<endl;
    else cout << res << endl;
    
    return 0;
}