[백준] 1103번: 게임

📌 문제

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

📌 설명

 전형적인 그래프 탐색 문제이지만, 사이클이 발생한 경우를 탐지해야 하므로 BFS 대신 DFS를 사용하는 것이 효율적이다. 그러나 단순히 DFS를 수행하며 동전이 움직일 수 있는 최대 횟수를 구하려고 하면 시간 초과가 발생하게 된다. 이미 방문한 지점인 경우, 추가적인 탐색을 진행하면 안 된다. 따라서 DP 배열을 추가로 선언해야 한다.

📌 코드

#include <iostream>
#include <algorithm>

using namespace std;

int ans = 0;
bool cycleFlag = false;
int n, m;
int board[50][50];
int visited[50][50];
int cnt[50][50];

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

bool OutofBound(int x, int y) {
	return x < 0 || y < 0 || x >= n || y >= m;
}

void dfs(int x, int y) {
	if (cycleFlag)
		return;

	ans = max(ans, cnt[x][y]);
	int num = board[x][y];

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i] * num;
		int ny = y + dy[i] * num;

		if (!OutofBound(nx, ny) && board[nx][ny] && cnt[x][y] + 1 > cnt[nx][ny]) {
			if (!visited[nx][ny]) {
				visited[nx][ny] = 1;
				cnt[nx][ny] = cnt[x][y] + 1;
				dfs(nx, ny);
				visited[nx][ny] = 0;
			}
			else {
				cycleFlag = true;
				ans = -1;
				return;
			}
		}
	}
}

int main() {
	cin >> n >> m;

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

			if (c == 'H')
				board[i][j] = 0;
			else
				board[i][j] = c - '0';
		}
	}

	cnt[0][0] = 1;
	visited[0][0] = 1;
	dfs(0, 0);

	cout << ans;
}

---

int ans = 0;
bool cycleFlag = false;
int n, m;
int board[50][50];
int visited[50][50];
int cnt[50][50];

ans는 동전이 움직일 수 있는 최대 횟수, cycleFlag는 사이클 발생 여부를 관리하는 flag이다. cnt 배열이 dp 배열이다.

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

			if (c == 'H')
				board[i][j] = 0;
			else
				board[i][j] = c - '0';
		}
	}

board를 초기화할 때 ‘H’는 0으로 초기화한다.

bool OutofBound(int x, int y) {
	return x < 0 || y < 0 || x >= n || y >= m;
}

void dfs(int x, int y) {
	if (cycleFlag)
		return;

	ans = max(ans, cnt[x][y]);
	int num = board[x][y];

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i] * num;
		int ny = y + dy[i] * num;

		if (!OutofBound(nx, ny) && board[nx][ny] && cnt[x][y] + 1 > cnt[nx][ny]) {
			if (!visited[nx][ny]) {
				visited[nx][ny] = 1;
				cnt[nx][ny] = cnt[x][y] + 1;
				dfs(nx, ny);
				visited[nx][ny] = 0;
			}
			else {
				cycleFlag = true;
				ans = -1;
				return;
			}
		}
	}
}

cycleFlag가 true인 경우 dfs를 진행하지 않고 리턴한다. 매 dfs 탐색마다 ans를 갱신한다.

nx, ny는 x, y의 인접 노드이다. cnt[x][y] + 1 > cnt[nx][ny] 조건식을 통해 불필요한 탐색을 방지할 수 있다. 현재 노드({x, y})에서 인접 노드({nx, ny})로 이동할 때, 새로운 경로의 횟수(cnt[x][y] + 1) 가 더 큰 경우에 cnt[nx][ny]를 업데이트한다.