728x90
 

11651번: 좌표 정렬하기 2

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

www.acmicpc.net

Java로 풀어보고 C++로도 풀어봤다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Loc> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            list.add(new Loc(in.nextInt(), in.nextInt()));
        }
        Collections.sort(list, new Comparator<Loc>() {
            @Override
            public int compare(Loc o1, Loc o2) {
                if(o1.y == o2.y)
                    return o1.x - o2.x;
                else
                    return o1.y - o2.y;
            }
        });
        for(Loc i : list)
            System.out.println(i);
    }
}
class Loc{
    int x;
    int y;

    public Loc(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return x + " " + y;
    }
}
#include <iostream> 
#include <vector> 
#include <queue> 
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v.push_back(make_pair(y, x));
	}
	sort(v.begin(), v.end());
	for (pair<int, int> p : v) {
		cout << p.second << " " << p.first << '\n';
	}
	return 0;
}

 

pair는 첫 번째 원소(first)를 기준으로 오름차순 정렬, first가 같으면 두 번째 원소(second)를 기준으로 오름차순 정렬

728x90
728x90
 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

www.acmicpc.net

BFS로 풀었다.

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

int n;
vector<int> countAll;
vector<int> allArea;

int main() {
	int m, n, k;
	cin >> m >> n >> k;
	vector<vector<int>> v(m);
	for (int i = 0; i < m; i++) 
		v[i] = vector<int>(n);
	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1; x < x2; x++) {
			for (int y = y1; y < y2; y++) {
				v[y][x] = 1;
			}
		}
	}
	vector<vector<bool>> visited(m);
	for (int i = 0; i < m; i++)
		visited[i] = vector<bool>(n);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (v[i][j] == 0 && !visited[i][j]) {
				queue < pair<int, int>> q;
				q.push(make_pair(i, j));
				int area = 0;
				while (!q.empty()) {
					pair<int, int> cur = q.front();
					q.pop();
					if (!visited[cur.first][cur.second] && v[cur.first][cur.second] == 0) {
						visited[cur.first][cur.second] = true;
						area++;
						if (cur.first + 1 < m && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 0) {
							q.push(make_pair(cur.first + 1, cur.second));
						}
						if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 0) {
							q.push(make_pair(cur.first - 1, cur.second));
						}
						if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 0) {
							q.push(make_pair(cur.first, cur.second + 1));
						}
						if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 0) {
							q.push(make_pair(cur.first, cur.second - 1));
						}
					}
				}
				allArea.push_back(area);
			}
		}
	}
	cout << allArea.size() << endl;
	sort(allArea.begin(), allArea.end());
	for (int i = 0; i < allArea.size(); i++) {
		cout << allArea[i] << " ";
	}
	return 0;
}
728x90
728x90
 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어

www.acmicpc.net

BFS로 풀었다.

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

int n;
vector<int> countAll;

int main() {
	countAll.push_back(1);
	cin >> n;
	vector<vector<int>> height(n);
	vector<vector<int>> rain(n);
	for (int i = 0; i < n; i++) {
		height[i] = vector<int>(n);
		rain[i] = vector<int>(n);
	}
	int maxHeight = 0;
	int minHeight = 101;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> height[i][j];
			if (height[i][j] > maxHeight) maxHeight = height[i][j];
			if (height[i][j] < minHeight) minHeight = height[i][j];
		}
	}
	for (int rainAmount = minHeight; rainAmount <= maxHeight; rainAmount++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (height[i][j] <= rainAmount) {
					rain[i][j] = 1;
				}
			}
		}

		int count = 0;
		vector<vector<bool>> visited(n);
		for (int i = 0; i < n; i++) {
			visited[i] = vector<bool>(n);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j] && rain[i][j] == 0) {
					count++;
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && rain[cur.first + 1][cur.second] == 0) {
								q.push(make_pair(cur.first + 1, cur.second));
							}
							if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && rain[cur.first - 1][cur.second] == 0) {
								q.push(make_pair(cur.first - 1, cur.second));
							}
							if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && rain[cur.first][cur.second + 1] == 0) {
								q.push(make_pair(cur.first, cur.second + 1));
							}
							if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && rain[cur.first][cur.second - 1] == 0) {
								q.push(make_pair(cur.first, cur.second - 1));
							}
						}
					}
				}
			}
		}
		countAll.push_back(count);
	}
	int maxCount = 0;
	for (int i : countAll)
		if (i > maxCount) maxCount = i;
	cout << maxCount;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 11651번 좌표 정렬하기 2  (0) 2020.02.06
[백준] 2583번 영역 구하기  (0) 2020.02.06
[백준] 10026번 적록색약  (0) 2020.02.06
[백준] 4153번 직각삼각형  (0) 2020.02.05
[백준] 3009번 네 번째 점  (0) 2020.02.05
728x90
 

10026번: 적록색약

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은

www.acmicpc.net

BFS로 풀었다.

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

int n;

int main() {
	cin >> n;
	vector<vector<char>> v(n);
	vector<vector<bool>> visited(n);
	for (int i = 0; i < n; i++) {
		v[i] = vector<char>(n);
		visited[i] = vector<bool>(n);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> v[i][j];
		}
	}
	int normalCount = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				normalCount++;
				if (v[i][j] == 'R') {
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'R') {
								q.push(make_pair(cur.first + 1, cur.second));
							}
							if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'R') {
								q.push(make_pair(cur.first - 1, cur.second));
							}
							if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'R') {
								q.push(make_pair(cur.first, cur.second + 1));
							}
							if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'R') {
								q.push(make_pair(cur.first, cur.second - 1));
							}
						}
					}
				}
				else if (v[i][j] == 'G') {
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'G') {
								q.push(make_pair(cur.first + 1, cur.second));
							}
							if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'G') {
								q.push(make_pair(cur.first - 1, cur.second));
							}
							if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'G') {
								q.push(make_pair(cur.first, cur.second + 1));
							}
							if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'G') {
								q.push(make_pair(cur.first, cur.second - 1));
							}
						}
					}
				}
				else if (v[i][j] == 'B') {
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'B') {
								q.push(make_pair(cur.first + 1, cur.second));
							}
							if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'B') {
								q.push(make_pair(cur.first - 1, cur.second));
							}
							if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'B') {
								q.push(make_pair(cur.first, cur.second + 1));
							}
							if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'B') {
								q.push(make_pair(cur.first, cur.second - 1));
							}
						}
					}
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = false;
			if (v[i][j] == 'G')
				v[i][j] = 'R';
		}
	}
	int abnormalCount = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				abnormalCount++;
				if (v[i][j] == 'R') {
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'R') {
								q.push(make_pair(cur.first + 1, cur.second));
							}
							if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'R') {
								q.push(make_pair(cur.first - 1, cur.second));
							}
							if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'R') {
								q.push(make_pair(cur.first, cur.second + 1));
							}
							if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'R') {
								q.push(make_pair(cur.first, cur.second - 1));
							}
						}
					}
				}
				else if (v[i][j] == 'B') {
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'B') {
								q.push(make_pair(cur.first + 1, cur.second));
							}
							if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'B') {
								q.push(make_pair(cur.first - 1, cur.second));
							}
							if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'B') {
								q.push(make_pair(cur.first, cur.second + 1));
							}
							if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'B') {
								q.push(make_pair(cur.first, cur.second - 1));
							}
						}
					}
				}
			}
		}
	}
	cout << normalCount << endl;
	cout << abnormalCount << endl;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2583번 영역 구하기  (0) 2020.02.06
[백준] 2468번 안전영역  (0) 2020.02.06
[백준] 4153번 직각삼각형  (0) 2020.02.05
[백준] 3009번 네 번째 점  (0) 2020.02.05
[백준] 10845번 큐  (0) 2020.02.05
728x90

그래프를 표현하는 방법은 크게 두 가지가 있다. 인접행렬과 인접리스트이다.

인접행렬은 많은 양의 메모리를 쓰는 대신에 정점 v1과 v2 사이에 간선이 있는지 없는지를 매우 빠르게 알아낼 수 있고 직관적이다.

인접 리스트는 적은 양의 메모리를 쓰고 정점 v1에 연결된 모든 정점들을 빨리 알아낼 수 있는 대신에 v1과 v2 사이에 이음선이 있는지 없는지는 빨리 알아내기 어렵다.

fully-connected 그래프가 아닌 이상 인접리스트로 구현하는 것이 좋다. 그런데 포인터로 구현하면 구조체를 구현해야 하고 사용법도 까다롭기 때문에 이미 구현된 라이브러리를 사용하는 방법을 소개하려고 한다.

벡터를 이용하면 쉽게 인접리스트를 구현할 수 있다.

만약 이런 그래프를 인접리스트로 표현하고 싶다면

vector<int> w[6]; //인덱스 0은 사용 안 함
w[1].push_back(2); //1에서 2로 향하는 이음선
w[1].push_back(4); //1에서 4로 향하는 이음선
w[2].push_back(3); //2에서 3로 향하는 이음선
w[3].push_back(4); //3에서 4로 향하는 이음선
w[4].push_back(2); //4에서 2로 향하는 이음선
w[4].push_back(5); //4에서 5로 향하는 이음선

이렇게 하면 된다.

 

만약 정점 1과 이음선으로 연결된 모든 정점을 출력하고 싶다면

for (int v : w[1]) {
	cout << v << endl;
}

 

이렇게 for-each문으로 w[1]에 저장되어 있는 모든 정점들을 순회하며 출력하면 된다.

(for-each문은 자바에만 있는 줄 알았었는데 C++에도 C++11부터 생겼다고 한다.)

1에 연결된 정점 2, 4를 출력하는 것을 볼 수 있다.

 

이렇게 벡터를 이용하면 포인터 없이, 직관적인 인접리스트를 구현할 수 있다.

이렇게 저장되어 있다고 이해하면 되는데

사실은 이렇게 저장되어 있다.

아무튼 다들 느꼈다시피 벡터로 구현해도 포인터를 이용한 인접리스트보다 편리하고 그만큼 직관적이다.

 

아래는 전체코드이다.

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

int main() {
	vector<int> w[6]; //인덱스 0은 사용 안 함
	w[1].push_back(2); //1에서 2로 향하는 이음선
	w[1].push_back(4); //1에서 4로 향하는 이음선
	w[2].push_back(3); //2에서 3로 향하는 이음선
	w[3].push_back(4); //3에서 4로 향하는 이음선
	w[4].push_back(5); //4에서 5로 향하는 이음선
	for (int v : w[1]) {
		cout << v << endl;
	}
	return 0;
}

출력결과는 아까 봤다시피 1에 인접한 정점 2, 4를 출력한다.

 

이를 이용한 DFS, BFS 등은 알고리즘 카테고리에 포스팅하겠습니다.

 

728x90
728x90
 

4153번: 직각삼각형

문제 과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오. 입력 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. 출력 각 입력에 대해 직각 삼각형이 맞다면 "right", 아니라면 "wrong"을 출력한다. 예제 입력 1 복사 6 8

www.acmicpc.net

#include <iostream>
using namespace std;


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	while (true) {
		int x, y, z;
		cin >> x >> y >> z;
		if (x == 0 && y == 0 && z == 0) break;
		if (x >= y && x >= z) {
			if (y * y + z * z == x * x) cout << "right" << '\n';
			else cout << "wrong" << '\n';
		}
		else if (y >= x && y >= z) {
			if (x * x + z * z == y * y) cout << "right" << '\n';
			else cout << "wrong" << '\n';
		}
		else if (z >= x && z >= y) {
			if(x * x + y * y == z * z) cout << "right" << '\n';
			else cout << "wrong" << '\n';
		}
	}
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2468번 안전영역  (0) 2020.02.06
[백준] 10026번 적록색약  (0) 2020.02.06
[백준] 3009번 네 번째 점  (0) 2020.02.05
[백준] 10845번 큐  (0) 2020.02.05
[백준] 1260번 DFS와 BFS  (0) 2020.02.04
728x90
 

3009번: 네 번째 점

문제 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. 입력 세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다. 출력 직사각형의 네 번째 점의 좌표를 출력한다. 예제 입력 1 복사 30 20 10 10 10 20 예제 출력 1 복사 30 10...

www.acmicpc.net

#include <iostream>
using namespace std;


int main() {
	int x1, y1, x2, y2, x3, y3, x4, y4;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
	if (x1 == x2) x4 = x3;
	else if (x1 == x3) x4 = x2;
	else if (x2 == x3) x4 = x1;
	if (y1 == y2) y4 = y3;
	else if (y1 == y3) y4 = y2;
	else if (y2 == y3) y4 = y1;
	cout << x4 << " " << y4;
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 10026번 적록색약  (0) 2020.02.06
[백준] 4153번 직각삼각형  (0) 2020.02.05
[백준] 10845번 큐  (0) 2020.02.05
[백준] 1260번 DFS와 BFS  (0) 2020.02.04
[백준] 1753번 최단경로  (0) 2020.02.04
728x90
 

10845번: 큐

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

www.acmicpc.net

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n; 
	cin >> n;
	queue<int> q;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		if (s == "push") {
			int num;
			cin >> num;
			q.push(num);
		}
		else if (s == "pop") {
			if (!q.empty()) {
				cout << q.front() << '\n';
				q.pop();
			}
			else cout << -1 << '\n';
		}
		else if (s =="empty") {
			cout << q.empty() << '\n';
		}
		else if (s == "size") {
			cout << q.size() << '\n';
		}
		else if (s == "front") {
			if (!q.empty())
				cout << q.front() << '\n';
			else cout << -1 << '\n';
		}
		else if (s == "back") {
			if (!q.empty())
				cout << q.back() << '\n';
			else cout << -1 << '\n';
		}
	}
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 4153번 직각삼각형  (0) 2020.02.05
[백준] 3009번 네 번째 점  (0) 2020.02.05
[백준] 1260번 DFS와 BFS  (0) 2020.02.04
[백준] 1753번 최단경로  (0) 2020.02.04
[백준] 11279번 최대 힙  (0) 2020.02.03
728x90
 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

www.acmicpc.net

파이썬과 C++로 풀어보았다.

두 언어 간 속도 차이는 엄청나다.

 

우선 파이썬으로 짠 코드이다. 그래프 클래스를 구현했다.

class Graph:
    def __init__(self, n):
        self.data = {}
        for i in range(1, n + 1):
            self.data[i] = set()
    def add_edge(self, n, m):
        self.data[n].add(m)
        self.data[m].add(n)
    def dfs(self, start):
        visited = [False] * (len(self.data) + 1)
        stack = []
        stack.append(start)
        while stack:
            cur = stack.pop()
            if not visited[cur]:
                print(cur, end=" ")
            visited[cur] = True
            temp = []
            for i in self.data[cur]:
                if not visited[i]:
                    temp.append(i)
            temp.sort()
            temp.reverse()
            stack.extend(temp)
    def bfs(self, start):
        import collections
        visited = [False] * (len(self.data) + 1)
        queue = collections.deque()
        queue.append(start)
        while queue:
            cur = queue.popleft()
            if not visited[cur]:
                print(cur, end=' ')
            visited[cur] = True
            temp = []
            for i in self.data[cur]:
                if not visited[i]:
                    temp.append(i)
            temp.sort()
            queue.extend(temp)
from sys import stdin

node_edge_start = list(map(int, stdin.readline().split()))
graph = Graph(node_edge_start[0])
li = []
for i in range(0, node_edge_start[1]):
    rawInput = list(map(int, stdin.readline().split()))
    graph.add_edge(rawInput[0], rawInput[1])
graph.dfs(node_edge_start[2])
print()
graph.bfs(node_edge_start[2])

 

C++로 짠 코드. 자식이 여러개라면 작은 수부터 방문한다는 조건이 있어서 <algorithm>의 sort() 함수를 이용해서 정렬해주었다.

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

bool cmp(int a, int b) {
	return a > b;
}

vector<int> w[1001];
int n, m, startNode;

void dfs() {
	vector<bool> visited(n + 1);
	stack<int> stack;
	stack.push(startNode);
	while (!stack.empty()) {
		int cur = stack.top();
		stack.pop();
		if (!visited[cur]) {
			cout << cur << " ";
		}
		visited[cur] = true;
		for (int v : w[cur]) {
			if (!visited[v])
				stack.push(v);
		}
	}
}
void bfs() {
	vector<bool> visited(n + 1);
	queue<int> q;
	q.push(startNode);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (!visited[cur])
			cout << cur << " ";
		visited[cur] = true;
		for (int v : w[cur]) {
			if (!visited[v]) {
				q.push(v);
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> startNode;
	int v1, v2;
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2;
		w[v1].push_back(v2);
		w[v2].push_back(v1);
	}
	for (int i = 1; i <= n; i++) {
		sort(w[i].begin(), w[i].end(), cmp);
	}
	dfs();
	cout << endl;
	for (int i = 1; i <= n; i++) {
		sort(w[i].begin(), w[i].end());
	}
	bfs();
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 3009번 네 번째 점  (0) 2020.02.05
[백준] 10845번 큐  (0) 2020.02.05
[백준] 1753번 최단경로  (0) 2020.02.04
[백준] 11279번 최대 힙  (0) 2020.02.03
[백준] 2581번 소수  (0) 2020.02.03
728x90
 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두

www.acmicpc.net

#include <iostream> 
#include <vector> 
#include <queue> 
#include <algorithm>
using namespace std;
vector<pair<int, int>> adj[20002];
int length[20002];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; //비용 적은 것이 우선이 되게 오름차순 정렬
bool visited[20002];

int main() {
	int numOfVertex, numOfEdge, startNode;
	cin >> numOfVertex >> numOfEdge >> startNode;
	const int INF = 2147483647;
	int from, to, weight;
	for (int i = 0; i < numOfEdge; i++) {
		cin >> from >> to >> weight;
		adj[from].push_back(pair<int, int>(weight, to)); //pair의 앞쪽에 있는 숫자를 기준으로 오름차순 정렬하므로 가중치를 앞에 둔다.
	}
	for (int i = 1; i <= numOfVertex; i++) {
		length[i] = INF;
	}
	length[startNode] = 0; //나에서 나로 가는 최단경로는 0
	q.push(make_pair(0, startNode));
	while (!q.empty()) {
		int cost = q.top().first;
		int now = q.top().second;
		q.pop();
		if (length[now] < cost || visited[now]) continue;
		visited[now] = true;
		for (int i = 0; i < adj[now].size(); i++) {
			if (length[adj[now][i].second] > adj[now][i].first + cost) {
				q.push(make_pair(adj[now][i].first + cost, adj[now][i].second));
				length[adj[now][i].second] = adj[now][i].first + cost;
			}
		}
	}
	for (int i = 1; i <= numOfVertex; i++) {
		if (length[i] >= INF) cout <<"INF\n";
		else cout << length[i] << '\n';
	}
	return 0;
}
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 10845번 큐  (0) 2020.02.05
[백준] 1260번 DFS와 BFS  (0) 2020.02.04
[백준] 11279번 최대 힙  (0) 2020.02.03
[백준] 2581번 소수  (0) 2020.02.03
[백준] 1427번 소트인사이드  (0) 2020.02.03

+ Recent posts