티스토리 뷰
728x90
문제 링크
https://www.acmicpc.net/problem/16724
지도 밖으로 나가는 방향의 입력이 주어지지 않고, 무조건 한 방향으로만 갈 수 있으므로 모든 노드는 싸이클에 포함되거나, 싸이클에 연결되어 있다.
싸이클을 이루는 그룹이 몇 개인지 세어주면 된다.
내가 푼 풀이는 말 그대로 싸이클의 수를 구하는 코드인데 설명하기가 애매하니 그냥 코드를 보자.
더 간단한 방법은 유니온파인드를 이용하면 된다!
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
728x90
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[BOJ] 백준 15361 Izbori (0) | 2019.05.13 |
---|---|
[BOJ] 백준 16211 백채원 (0) | 2019.05.13 |
[BOJ] 백준 16723 원영이는 ZOAC과 영원하고 싶다 (1) | 2019.01.20 |
[BOJ] 백준 16722 결! 합! (1) | 2019.01.20 |
[BOJ] 백준 16721 Structure of Balanced Networks (1) | 2019.01.20 |