[백준] 16964 DFS 스페셜 저지
2021. 2. 20. 20:39
Problem set
16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net #include #include #include #include using namespace std; vector a[100000]; bool check[100000]; vector dfs_order; void dfs(int x) { if (check[x]) return; dfs_order.push_back(x); check[x] = true; for (int y : a[x]) { dfs(y); } } int main() { i..
[백준] 16940 BFS 스페셜 저지
2021. 2. 20. 20:37
Problem set
16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net #include #include #include using namespace std; vector a [100000]; int parent[100000]; int order[100000]; bool check[100000]; int main() { int n; cin >> n; for (int i=0; i> u >> v; u -= 1; v -= 1; a[u].push_back(v); a[v].push_back(u); } for (int i=0; i> order[i]; order[i] -= 1; } queue q; q.push(0); check[0] = true; int m = 1..
[백준] 7562 나이트의 이동
2021. 2. 20. 20:34
Problem set
7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net #include #include #include using namespace std; int d[300][300]; int dx[] = {-2,-1,1,2,2,1,-1,-2}; int dy[] = {1,2,2,1,-1,-2,-2,-1}; int main() { int t; cin >> t; while (t--) { int n; cin >> n; int sx,sy; cin >> sx >> sy; int ex,ey; cin >> ex >> ey; memset(d,-1..
[백준] 7576 토마토
2021. 2. 20. 20:33
Problem set
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net #include #include using namespace std; int a[1000][1000]; int d[1000][1000]; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int main() { int n,m; scanf("%d %d",&m,&n); queue q; for (int i=0; i
[백준] 2178 미로 탐색
2021. 2. 20. 20:31
Problem set
2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #include #include using namespace std; int n,m; int a[100][100]; bool check[100][100]; int dist[100][100]; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int main() { scanf("%d %d",&n,&m); for (int i=0; i
[백준] 4963 섬의 개수
2021. 2. 20. 20:30
Problem set
4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #include #include #include using namespace std; int a[100][100]; int d[100][100]; int dx[] = {0,0,1,-1,1,1,-1,-1}; int dy[] = {1,-1,0,0,1,-1,1,-1}; int n,m; void bfs(int x, int y, int cnt) { queue q; q.push(make_pair(x,y)); d[x][y] = cnt; while (!q.empty())..
[백준] 2667 단지번호붙이기
2021. 2. 20. 20:28
Problem set
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net #include #include #include using namespace std; int a[30][30]; int group[30][30]; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int n; int ans[25*25]; void bfs(int x, int y, int cnt) { queue q; q.push(make_pair(x,y)); group[x][y] = cnt; while (!q.empty()) { x =..
[백준] 1707 이분 그래프
2021. 2. 20. 20:26
Problem set
1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net #include #include #include #include #include using namespace std; vector a[20001]; int color[20001]; void dfs(int node, int c) { color[node] = c; for (int i=0; i