<문제> 백준 16929번 : Two Dots
https://www.acmicpc.net/problem/16929
무방향 그래프의 사이클을 detection하는 문제이다.
사이클이 있으면 Yes, 없으면 No를 출력한다.
<풀이> 무방향 그래프 사이클 detection 방법
가장 바깥 쪽부터 지워나가는 테크닉을 이용하였다.
아래와 같이 indegree배열을 선언해주고, 간선의 길이가 1인 배열 먼저 큐에 모두 넣어준다.
이후 위상 정렬과 비슷한 방법으로 가장 가장자리의 노드를 하나씩 지운다.
위 과정을 수행하고도 indegree가 2보다 크면 사이클이 존재한다는 것이다.
<구현>
필자는 조금 야메로 구현해서 이 프로그램 돌려보면 간선의 길이가 음수인 노드가 많다.
참고만 하고 이렇게 구현하지 말자.
|
1
2
|
#include<bits/stdc++.h>
using namespace std;
const int dx[] = { 0, 1, 0, –1 };
const int dy[] = { 1, 0, –1, 0 };
typedef pair<int, int> pii;
int arr[60][60];
int n, m;
bool visited[60][60];
int indeg[60][60];
int main(){
scanf(“%d %d”, &n, &m);
getchar();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
char ch; ch = getchar();
arr[i][j] = ch – ‘A’ + 1;
}
getchar();
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int k = 0; k < 4; k++){
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(arr[i][j] == arr[nx][ny]){
indeg[i][j]++;
indeg[nx][ny]++;
}
}
}
}
for(int i = 0; i <n; i++){
for(int j = 0; j < m; j++) indeg[i][j] /= 2;
}
queue<pii> q;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(indeg[i][j] == 1) q.push({i, j});
}
}
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
indeg[x][y]––;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(arr[x][y] == arr[nx][ny]){
indeg[nx][ny]––;
if(indeg[nx][ny] == 1) q.push({nx, ny});
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(indeg[i][j] >= 2){
printf(“Yes”);
return 0;
}
}
}
printf(“No”);
}
|
cs |
Leave a Reply
Your email is safe with us.