취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1103번 문제인 게임이다.
문제는 아래 링크를 확인하자.

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

주어진 게임은 각 칸을 노드로, 한 칸에서 다른 칸으로 이동할 수 있는 관계를 방향이 있는 에지로 생각해 방향그래프로 모델링할 수 있다.

출발 칸에서 시작해 어떤 사이클에 빠질 수 있다면 -1을, 그렇지 않다면 주어진 그래프는 DAG이므로 위상정렬순 탐색을 통해 이동할 수 있는 최장거리를 구해 문제를 해결하자.

아래는 제출한 소스코드이다.

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


int R, C;
string board[50];
int visited[50][50];
int dist[50][50];
bool chk = 0;

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void dfs(int r, int c) {
	visited[r][c] = 1;
	int d = board[r][c] - '0';
	for (int i = 0; i < 4; i++) {
		int rr = r + dr[i] * d, cc = c + dc[i] * d;
		if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == 'H') continue;
		if (visited[rr][cc]) {
			if (visited[rr][cc] == 1) chk = 1;
		}
		else dfs(rr, cc);
	}

	visited[r][c] = 2;
}

int indegree[50][50];

void init() {
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (!visited[r][c]) continue;
			int d = board[r][c] - '0';
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i] * d, cc = c + dc[i] * d;
				if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == 'H') continue;
				indegree[rr][cc]++;
			}
		}
	}
}

void dfs2(int r, int c) {
	int d = board[r][c] - '0';
	for (int i = 0; i < 4; i++) {
		int rr = r + dr[i] * d, cc = c + dc[i] * d;
		if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == 'H') continue;
		dist[rr][cc] = max(dist[rr][cc], dist[r][c] + 1);
		indegree[rr][cc]--;
		if (indegree[rr][cc] == 0) dfs2(rr, cc);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	dfs(0, 0);

	if (chk) cout << -1;
	else {
		init();
		dist[0][0] = 1;
		dfs2(0,0);
		int ans = 0;
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				ans = max(ans, dist[r][c]);
			}
		}

		cout << ans;
	}
}