congcoding

1. 문제 링크

www.acmicpc.net/problem/1753

2. 문제 설명

가중치가 있는 방향 그래프의 정점의 개수, 간선의 개수, 시작 정점의 번호, 간선을 입력받아

시작점에서 다른 모든 정점으로의 최단 거리를 출력하는 문제입니다.

한 정점에서 다른 모든 정점으로의 최단 거리를 구하는 문제이고,

가중치가 10 이하의 자연수(음수가 아님)이기 때문에 다익스트라 알고리즘을 사용했습니다.

다익스트라 알고리즘의 개념과 코드는 아래 링크를 참고했습니다.

blog.encrypted.gg/918?category=773649

3. 소스코드

BOJ 1753번 최단경로 C++ 풀이입니다.

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

int dis[20001];
const int INF = 2147483647;
vector<pair<int, int> > adj[20001];

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

	int V, E, K;
	cin >> V >> E >> K;
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back(make_pair(w, v));
	}
	fill(dis, dis + V + 1, INF);

	dis[K] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.push(make_pair(dis[K], K));
	while (!pq.empty()) {
		pair<int, int> cur = pq.top();
		pq.pop();
		int dist = cur.first;
		int idx = cur.second;
		if (dis[idx] != dist)
			continue;
		for (int i = 0; i < adj[idx].size(); i++) {
			pair<int, int> next = adj[idx][i];
			int cost = next.first;
			int nidx = next.second;
			if (dis[nidx] > dist + cost) {
				dis[nidx] = dist + cost;
				pq.push(make_pair(dis[nidx], nidx));
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		if (dis[i] == INF)
			cout << "INF\n";
		else
			cout << dis[i] << "\n";
	}

	return 0;
}

7번 라인 : 시작점에서 다른 모든 정점으로의 최단거리를 저장할 배열 dis를 선언합니다. 정점의 최대 개수가 20000이므로 dis[20000]으로 접근할 수 있도록 20001의 크기로 선언했습니다.

8번 라인 : 무한대를 표현하기 위해 int의 최댓값을 INF라는 상수로 선언했습니다.

9번 라인 : 간선을 인접리스트형태로 저장하기 위해 vector 배열 adj을 선언했습니다. 정점 번호와 가중치를 함께 저장해야 하기 때문에 pair를 사용했습니다.

20번 라인 : 입력받은 간선을 adj에 추가합니다. 아래에서 priority queue를 사용하여 min heap을 만들 때 가중치를 기준으로 정렬해야 하므로 가중치(w), 정점 번호(v)순으로 pair를 만들어서 추가합니다.

22번 라인 : dis배열을 INF로 초기화합니다.

24번 라인 : 시작점에서 시작점으로의 거리는 문제에서 제시한대로 0으로 바꿔줍니다.

25번 라인 : priority_queue를 선언합니다. priority_queue<자료형, 구현체, 비교 연산자>의 형태로 사용해야 하므로 구현체는 기본값인 vector를 사용했고, 비교 연산자는 greater를 사용하여 min heap을 만들었습니다. (참고 링크 : koosaga.com/9)

26번 라인 : pq에 시작점을 추가합니다.

27번 라인 : 힙이 비어있지 않는 동안

28 ~ 31번 라인 : 가중치가 가장 작은 간선을 꺼내서 dis에 가중치를, idx에 정점을 저장합니다.

32 ~ 33번 라인 : dis[idx]와 dist가 다르면, 이전에 저장할 때보다 더 짧은 경로를 찾은 것이므로 continue합니다.

34번 라인 : 인접 리스트에서 idx번 정점과 연결되어 있는 간선을 모두 돌면서

35 ~ 37번 라인 : cost에 가중치, nidx에 다음 정점을 저장하고,

38번 라인 : 현재 저장되어 있는 최단 거리(dis[nidx])보다 dist + cost한 값이 작으면

39 ~ 40번 라인 : dis[nidx]에 dist + cost를 저장하여 최단 거리를 갱신하고, pq에 추가합니다.

44 ~ 49번 라인 : 1번 정점부터 V번 정점까지 돌면서 경로가 존재하지 않는 경우에는 INF를 출력하고, 시작점부터 i번째 점까지의 최단 거리를 출력합니다.

1. 문제 링크

www.acmicpc.net/problem/2178

2. 문제 설명

도착점(N, M)과 0(이동할 수 없는 칸)과 1(이동할 수 있는 칸)로 이루어진 미로를 입력받은 후,

출발점(1, 1)에서 도착점까지 최단 거리를 출력하는 문제입니다. 따라서 bfs를 사용해야 합니다.

칸을 셀 때에는 시작 위치와 도착 위치도 포함해야 합니다.

3. 소스코드

BOJ 2178번 미로 탐색 C++ 풀이입니다.

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

string map[100];
int dis[100][100];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

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

	int N, M;
	queue<pair<int, int> > q;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	q.push(make_pair(0, 0));
	dis[0][0] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < N && 0 <= ny && ny < M
			&& dis[nx][ny] == 0 && map[nx][ny] == '1') {
				q.push(make_pair(nx, ny));
				dis[nx][ny] = dis[x][y] + 1;
			}
		}
	}
	cout << dis[N - 1][M - 1];

	return 0;
}

5번 라인 : 미로를 이루고 있는 수들은 붙어서 입력으로 주어지므로 string을 이용하여 한 줄씩 처리하기 위해 string배열을 선언했습니다.

6번 라인 : 방문여부를 체크하고, 거리를 저장할 배열 dis를 이차원 배열로 선언합니다.

7, 8번 라인 : 미로를 그래프로 생각해보면 연결된 정점은 상, 하, 좌, 우 이므로 4방향 좌표를 미리 선언합니다.

15번 라인 : 좌표 형식으로 이루어져 있으므로 queue<pair<int, int>>로 선언합니다.

17, 18번 라인 : 미로를 한줄씩 입력받아 string 배열인 map에 저장합니다.

20번 라인 : 시작점을 make_pair(0, 0)을 이용해 만든 후 q에 push합니다.

21번 라인 : 시작점도 칸을 셀 때 포함해야 하므로 dis[0][0]을 1로 바꿔줍니다.

22번 라인 : q가 비어있지 않는 동안

23번 라인 : x에 현재 방문한 x좌표(q.front().first)를 저장합니다.

24번 라인 : y에 현재 방문한 y좌표(q.front().second)를 저장합니다.

25번 라인 : q.pop()을 이용하여 q에서 빼주고,

26번 라인 : 총 4번(상, 하, 좌, 우) 돌면서

27번 라인 : nx에 다음에 방문할 x좌표(x + dx[i])를 저장하고,

28번 라인 : ny에 다음에 방문할 y좌표(y + dy[i])를 저장합니다.

29번 라인 : nx와 ny가 미로의 범위 안에 있고,

30번 라인 : nx, ny를 방문한 적이 없고 (dis[nx][ny] == 0), 이동할 수 있는 칸(map[nx][ny] == '1')이면,

31번 라인 : make_pair(nx, ny)를 이용해 q에 push한 후,

32번 라인 : dis[nx][ny]는 현재 방문한 좌표의 거리(dis[x][y])에 1을 더하여 저장합니다.

36번 라인 : bfs를 이용했으므로 dis[N - 1][M - 1]에는 (0,0)에서 (N, M)까지의 최단 거리가 저장되어 있고, 이를 출력합니다.

1. 문제 링크

www.acmicpc.net/problem/2606

2. 문제 설명

컴퓨터(정점)의 수, 연결되어 있는 컴퓨터 쌍(간선)의 수, 연결되어 있는 컴퓨터의 번호 쌍(간선이 연결하는 두 정점의 번호)를 입력받아서

1번 컴퓨터(정점)에 연결되어 있는 컴퓨터의 수(정점의 수)를 출력하는 문제입니다.

3. 소스코드

BOJ 2606번 바이러스 C++ 풀이입니다.

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

vector<int> e[101];
bool check[101];

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

	int cn, pn, from, to, cnt = 0;
	queue<int> q;
	cin >> cn >> pn;
	for (int i = 0; i < pn; i++) {
		cin >> from >> to;
		e[from].push_back(to);
		e[to].push_back(from);
	}

	q.push(1);
	check[1] = true;
	while(!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < e[cur].size(); i++) {
			int next = e[cur][i];
			if (!check[next]) {
				check[next] = true;
				q.push(next);
				cnt++;
			}
		}
	}
	cout << cnt;

	return 0;
}

6번 라인 : 인접 리스트를 저장할 vector를 정점의 최대 개수가 100이므로 e[100]으로 접근할 수 있도록 101의 크기로 선언했습니다.

7번 라인 : 정점의 방문을 체크할 배열 check도 마찬가지 이유로 101의 크기로 선언했습니다.

15번 라인 : 컴퓨터의 개수를 cn, 컴퓨터 쌍의 수를 pn에 저장합니다.

16 ~ 20번 라인 : 컴퓨터는 서로 연결되어 있으므로 인접 리스트에 양방향으로 저장합니다.

22번 라인 : 1번 컴퓨터를 방문하기 위해 q에 1을 push하고,

23번 라인 : check[1]을 true로 변경하면서 방문한 것을 표시합니다.

24번 라인 : q가 비어있지 않는 동안

25번 라인 : cur변수에 현재 방문한 정점을 q.front()를 이용하여 저장하고,

26번 라인 : q.pop()을 이용하여 q에서 빼주고,

27번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,

28번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장하고,

29번 라인 : next정점을 방문한 적이 없으면(check[next] == false)

30번 라인 : next정점을 방문하였다고 표시한 후(check[next] = true)

31번 라인 : q에 next정점을 push하고

32번 라인 : 1번 컴퓨터와 연결된 컴퓨터의 개수(cnt)를 1 증가시킵니다.

36번 라인 : 최종 결과(cnt)를 출력합니다.