Computer Science & Engineering

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

이 문제는 BFS와 DFS모두 풀 수 있는 문제이다. 문제 알고리즘 분류는 깊이 우선 탐색이지만 글쓴이는 BFS를 이용하여 풀었다. 문제는 인접행렬이 주어졌을 때 2-친구의 수가 가장 많은 사람을 구하는 것이다. 2-친구는 두 사람이 친구이거나 한 사람을 건너서 친구인 친구를 말한다. 즉 깊이가 2 이하로 알고 있는 친구의 수이다. 코드는 다음과 같다.

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

const int MN = 51;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int rst = 0;
    int N; cin >> N;
    for(int i = 0; i < N; i++) {
        string s; cin >> s; //한 줄씩 string으로 입력 받음
        for(int j = 0; j < s.size(); j++) {
            if(s[j] == 'Y') { //친구인 경우 인접리스트에 추가
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    for(int i = 0; i < N; i++) { //0번부터 N-1번까지 2-친구의 수 구하기
        queue<int> q; //BFS에 이용할 큐
        memset(vst, 0, sizeof(vst)); //방문배열 초기화
        vst[i] = true; //자기 자신 방문 체크
        int cnt = 0;
        for(int e : g[i]) { //자기 자신의 친구 체크
            if(!vst[e]) {
                vst[e] = 1;
                cnt++;
                q.push(e);
            }
        }
        while(!q.empty()) { //자기 자신의 친구의 친구들만 확인
            int now = q.front(); q.pop();
            for(int e : g[now]) {
                if(!vst[e]) { //친구가 아닌 경우. 즉 친구의 친구인 경우
                    vst[e] = 1;
                    cnt++;
                }
            }
        }
        rst = max(rst, cnt); //2-친구가 가장 많은 사람의 2-친구 수 갱신
    }
    cout << rst;
}

이 문제는 깊이를 확인할 필요 없이 깊이가 2까지만 탐색하면 되므로 0번부터 N-1번까지의 친구를 큐에 넣고 수를 세고 큐가 빌 때까지 그 친구들의 친구의 수만 세주면 된다. 이때 친구의 친구를 발견할 경우 큐에 넣지 않으면 깊이가 2인 친구까지만 탐색할 수 있다. 그렇게 구한 2-친구의 수의 최대값을 출력하면 간단히 답을 구할 수 있다.

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

이 문제는 비 방향성 그래프의 간선이 주어졌을 때 V번 정점부터 시작하여 DFS로 탐색한 결과와 BFS로 탐색한 결과를 각각 출력하는 기본적인 그래프 탐색 문제이다. 입력은 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점 번호 V와 M개의 간선들로 이루어진다. 코드는 아래와 같다.

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

const int MN = 1001;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문 여부
void dfs(int N) { //DFS
    vst[N] = true; //방문 체크
    cout << N << ' '; //방문한 노드 번호 출력
    for(int e : g[N]) { //방문한 노드로부터 인접 리스트를 확인
        if(!vst[e]) dfs(e); //방문하지 않은 노드 방문
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, V; cin >> N >> M >> V;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //인접리스트 추가
        g[v].push_back(u);
    }
    for(int i = 1; i <= N; i++) { //정점 번호 오름차순으로 정렬
        sort(g[i].begin(), g[i].end());
    }
    dfs(V); //V번 정점부터 DFS
    cout << "\n" << V; //DFS출력 마지막을 나타내는 개행 후 BFS 시작정점 V출력
    queue<int> q; //BFS에 사용할 queue
    memset(vst, 0, sizeof(vst)); //방문 배열 초기화
    q.push(V); //시작 정점 queue에 추가
    vst[V] = true; //시작 정점 방문 체크
    while(!q.empty()) { //모든 정점을 방문할 때까지
        int now = q.front(); q.pop(); //queue의 첫 번째 pop
        for(int e : g[now]) { //인접리스트 확인
            if(!vst[e]) { //방문하지 않은 노드 발견할 경우
                cout << ' ' << e; //정점 출력
                vst[e] = 1; //방문 체크
                q.push(e); //queue에 추가
            }
        }
    }
}

방문하는 정점은 번호가 작은 것부터 우선적으로 방문해야하므로 우선 각 정점의 인접리스트를 오름차순으로 정렬한다.

    DFS를 우선적으로 출력하기 때문에 방문하지 않은 노드를 발견할 경우 곧바로 DFS로 탐색하여 정점을 출력하고 방문체크를 한다. 그 다음 그 노드로부터 인접리스트를 확인하여 더 탐색할 수 있는 정점이 있는지 확인한다. 있을 경우 재귀적으로 탐색한다.

    BFS는 queue를 이용한다. 방문한 노드를 체크하고 큐에 넣는다. 큐는 FIFO(First In First Out)이기 때문에 방문한 노드를 순서대로 확인할 수 있다. 시작정점 V를 큐에 넣고 방문 체크를 한다. 반복문은 큐가 빌때까지 반복한다. 큐의 첫 번째 원소를 pop한 후 그 원소의 인접 리스트를 확인한다. 방문하지 않은 노드를 발견할 경우 그 정점을 출력하고 방문체크를하고 큐에 push한다.

    백준에서는 개행이나 공백이 한 두개 더 출력되더라도 오답처리를 하지 않기 때문에 마지막일 경우 뒤에 공백이나 개행을 넣지 않기 위한 예외를 처리하지 않아도 된다.

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

이 문제는 BFS와 DFS 모두 풀 수 있는 문제이다. 글쓴이는 DFS를 이용하여 이 문제를 풀어보았다. 코드는 아래와 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stdbool.h>
#include <vector>
#include <cstring>

using namespace std;

const int MN = 51;

int map[MN][MN]; //인접행렬
bool vst[MN][MN]; //방문 여부
int di[8] = {1, 0, 0, -1, 1, -1, 1, -1}; //8가지 방향으로 이동을 나타냄
int dj[8] = {0, 1, -1, 0, 1, 1, -1, -1};
int w, h;
void dfs(int i, int j) {
    vst[i][j] = true; //방문 체크
    for(int d = 0; d < 8; d++) { //8가지 방향을 탐색
        int ni = i + di[d]; //다음 i좌표
        int nj = j + dj[d]; //다음 j좌표
        if(0 <= ni && ni < h && 0 <= nj && nj < w) { //지도를 벗어나는지 확인
            if(!vst[ni][nj] && map[ni][nj]) { //방문 여부와 땅인지 여부 확인
                dfs(ni, nj); //재귀로 DFS 탐색
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    while(true) { //0을 입력받을 때까지 반복
        cin >> w >> h;
        if(w == 0 && h == 0) break; //0이 두 개 입력될 경우 종료
        memset(map, 0, sizeof(map)); //테스트케이스마다 초기화
        memset(vst, 0, sizeof(vst)); //테스트케이스마다 초기화
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                cin >> map[i][j]; //지도 입력
            }
        }
        int cnt = 0;
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(map[i][j] && !vst[i][j]) { //땅이고 방문하지 않은 경우 DFS 탐색
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }
}

이 문제는 지도를 주어졌을 때 상하좌우 대각선으로 땅이 이어져 있다고 할 때 분리된 섬의 개수를 구하는 문제이다. 우리는 x, y좌표 형식으로 문제를 입력받기 때문에 위 코드의 di, dj 배열과 같이 8가지 방향을 나타낼 수 있다. 그림으로 나타내면 다음과 같이 나타낼 수 있다.

i, j에서 8가지 방향의 좌표를 더해 ni, nj 좌표를 구한다. 이때 지도를 벗어나는지를 확인해준다. 그렇지 않으면 Out of Bounds 에러가 발생할 수 있다.  그 다음 방문 여부와 땅인지의 여부를 확인하여 DFS 탐색을 계속한다. 이때 지도에서 땅인 부분의 DFS 횟수가 곧 섬의 개수인 것을 알 수 있다. 이전에 풀은 연결 요소의 개수와 구하는 방식이 비슷한 것을 알 수 있다. 차이점은 인접리스트 형식이 아니라 좌표형식으로 주어진 입력을 활용하여 좌표를 이동하며 DFS를 한다는 것이다.

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

이 문제는 방향이 없는 그래프를 주어졌을 때, 연결 요소의 개수를 구하는 문제이다. 즉 간선으로 연결되어 있는 집합의 개수가 총 몇 개인지를 출력하는 프로그램이다. bfs, dfs 모두 사용할 수 있는 문제지만 나는 dfs를 이용하였다. 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

bool visit[1001]; //방문 여부 판단
vector<int> g[1001]; //인접 리스트
void dfs(int n) { //DFS 함수
    visit[n] = 1;
    for(int nxt : g[n]) {
        if(!visit[nxt])
            dfs(nxt);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); //시간 감소
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //비방향성 그래프이므로 인접 리스트에 u->v, v->u 모두 추가
        g[v].push_back(u);
    }
    int cnt = 0;
    for(int i = 1; i <= N; i++) { //1부터 N까지 dfs를 하며 연결 요소의 개수 카운트
        if(!visit[i]) { //방문하지 않은 번호에서만 dfs
            dfs(i);
            cnt++;
        }
    }
    cout << cnt;
}

이 문제는 가장 간단한 DFS 문제중 하나이다. 1번 노드부터 N번 노드까지 DFS를 이용해 전부 방문하고 나면 visit 배열을 통해 방문한 노드인지 확인할 수 있다. 그러므로 이미 방문한 DFS의 횟수를 통해 연결 요소의 개수를 셀 수 있다.

인접 행렬은 인접 리스트에 비해 많은 메모리를 소모하기 때문에 vector를 지원하는 C++에서는 인접 리스트를 사용하는 것이 굉장히 좋다. DFS에서 재귀를 이용해 탐색할 때 방문 여부를 언제 체크하냐에 따라 재귀의 횟수를 많이 줄일 수 있다. 위와 같이 재귀를 하기 전에 방문 여부를 확인할 경우가 있고 재귀를 들어가서 첫 줄에 방문했을 경우 return하는 방식으로 프로그램을 구현할 수 있다. 후자의 경우 불필요한 방문이 될 수 있으므로 위의 코드와 같이 전자 방식으로 구현하는 것이 더 효율적이다.

최단 경로를 탐색하는 알고리즘에서 한 정점에서 다른 모든 정점까지 탐색하는 알고리즘에는 대표적으로 두 가지가 있다. 하나는 다익스트라 알고리즘이고 다른 하나는 벨만-포드 알고리즘이다. 두 알고리즘의 차이점은 대부분 알다시피 간선의 가중치에 음수가 있느냐(벨만-포드) 없느냐(다익스트라)이다.

이 점은 누구나 알고 있지만 실제로 코드에서 어떠한 차이점이 있는 지는 설명만 보고 알기 어려워 비교를 해보려고 한다.

우선 대표적인 다익스트라 알고리즘 문제인 백준 1753번 문제를 푼 알고리즘이다.

www.acmicpc.net/problem/1753 

다익스트라 알고리즘

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int INF = 2123456789;

struct edge { //간선의 가중치와 목적지 구조체
	int w, v;
};

vector<edge> g[20001]; //그래프 간선 구조체
int dist[20001]; //시작점에서 모든 정점까지의 최단 경로를 저장할 dp배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
	int V, E, K; cin >> V >> E >> K;
	for(int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({w, v}); //그래프의 간선 정보 입력
	}

	fill(dist + 1, dist + 1 + V, INF); //시작점에서 모든 정점은 아직 방문하지 않았으므로 INF로 초기화

	using P = pair<int,int>; //pair 표현 간소화
	priority_queue<P, vector<P>, greater<P>> pq; //최소힙 구현
	pq.push({0, K}); //처음 시작점 push
	dist[K] = 0; //시작점은 최단 경로 0으로 초기화
	while(!pq.empty()) { //더 이상 갱신할 최단 경로가 없을 때까지
		P tmp = pq.top(); pq.pop(); //새로 뻗을 수 있는 간선 중에 가중치가 가장 작은 값
		int cur_w = tmp.first;
		int cur = tmp.second;

		if(dist[cur] < cur_w) continue; //최소값 아닐 경우 건너뛰기

		for(edge next : g[cur]) { //새로 뻗은 간선에서 뻗을 수 있는 모든 간선에 대하여
			if(dist[next.v] > dist[cur] + next.w) { //최소값을 갱신할 수 있으면 갱신하고 우선순위 큐에 push
				dist[next.v] = dist[cur] + next.w;
				pq.push({dist[next.v], next.v});
			}
		}
	}
	for(int i = 1; i <= V; i++) {
		if(dist[i] == INF) //최단 경로가 없으면 INF
			cout << "INF" << '\n';
		else
			cout << dist[i] << '\n'; //최단 경로가 있으면 최단 경로 출력
	}
	return 0;
}

www.acmicpc.net/problem/11657

벨만 포드 알고리즘

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

struct edge { //간선의 정보를 저장할 구조체
    long long w, v;
};

int INF = 987654321;
vector<edge> g[501]; //그래프 간선 표현 vector배열
long long dist[501]; //최소값을 저장할 dp배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        long long a, b, c; cin >> a >> b >> c;
        g[a].push_back({c, b}); //간선 정보 저장
    }
    fill(dist, dist+N+1, INF); //모든 정점까지 최단 경로 INF로 초기화
    dist[1] = 0; //시작점 최단 경로 0으로 초기화

    for(int i = 1; i <= N; i++) { //N번 반복
        for(int j = 1; j <= N; j++) { //j에서 다른 정점으로 뻗을 수 있는 간선의 정점 최솟값 갱신
            if(dist[j] == INF) continue; //최단 경로가 없는 경우 건너뛰기
            for(edge next : g[j]) { //j에서 뻗을 수 있는 간선에 대하여
                if(i < N) { //모든 정점 갱신할 수 있는 N-1번 반복까지는 최단 경로 갱신
                    if(dist[next.v] > dist[j] + next.w) { //최단 경로 갱신
                        dist[next.v] = dist[j] + next.w;
                    }
                }
                else { //만약 모든 최단 경로를 갱신한 다음 N번째에도 최솟값을 갱신하는 경우
                    if(dist[next.v] > dist[j] + next.w) { //무한히 최단 경로를 갱신하므로 -1출력하고 프로그램 종료
                        cout << -1 << '\n';
                        return 0;
                    }
                }
                
            }
        }
    }
    for(int i = 2; i <= N; i++) {
        if(dist[i] == INF) cout << -1 <<'\n'; //최단 경로가 없는 경우 -1 출력
        else cout << dist[i] <<'\n'; //최단 경로 출력
    }

}

위와 같이 두 가지 알고리즘을 작성해보았다.

간선에 음의 가중치가 없는 다익스트라의 경우 최솟값이 무한히 갱신되는 경우가 없기 때문에

우선순위 큐를 이용하여 갱신할 최단 경로가 존재하지 않을 때까지만 반복하면 된다.

하지만 음의 가중치가 있는 벨만 포드의 경우 다익스트라처럼 우선순위 큐를 사용할 경우

최단 경로를 갱신하는 경우 우선선위 큐에 push하고 큐가 모두 빌 때까지 반복하므로 아래 그림과 같이 1에서 4까지의 경로가 2-3-4를 순환하면서 최단경로가  -1씩 무한히 갱신될 수 있다.

따라서 정점의 수 N에 대하여 간선의 수는 최대 N(N-1)이므로 모든 정점에 대하여 N-1번 반복하면 모두 갱신할 수 있게 된다. 따라서 N번째 반복에서 최단 경로가 또 한 번 갱신된다면 이는 위의 그림처럼 무한히 갱신되는 경우가 된다.

이러한 이유가 벨만 포드에서 우선순위 큐가 빌 때까지가 반복문의 조건이 아닌 이유이다.