티스토리 뷰

728x90

문제 링크

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

 

지도 밖으로 나가는 방향의 입력이 주어지지 않고, 무조건 한 방향으로만 갈 수 있으므로 모든 노드는 싸이클에 포함되거나, 싸이클에 연결되어 있다.

싸이클을 이루는 그룹이 몇 개인지 세어주면 된다.

 

내가 푼 풀이는 말 그대로 싸이클의 수를 구하는 코드인데 설명하기가 애매하니 그냥 코드를 보자.

 

더 간단한 방법은 유니온파인드를 이용하면 된다!

 

 

정답 코드

#include <iostream>
using namespace std;
char dtoi[200];
int p[1001][1001], chk[1001][1001], n, m;
int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
int dfs(int x, int y, int lev) {
if (chk[x][y]) return chk[x][y];
chk[x][y] = lev;
return chk[x][y] = dfs(x + dx[p[x][y]], y + dy[p[x][y]], lev);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
dtoi['R'] = 0; dtoi['D'] = 1; dtoi['L'] = 2; dtoi['U'] = 3;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char x;
cin >> x;
p[i][j] = dtoi[x];
}
}
int ans = 0, lev = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = dfs(i, j, lev);
if (x == lev) lev++;
}
}
cout << lev - 1;
}
view raw 16724.cpp hosted with ❤ by GitHub

 

728x90
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
글 보관함