프로그래밍
-
백준 13549 (숨바꼭질 3)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 26. 18:27
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 해당 문제는 수빈이의 위치와 동생의 위치가 주어질 때 수빈이가 동생을 찾을 수 있는 가장 빠른 경우의 시간을 찾는 문제이다. 이때 수빈이의 이동할 수 있는 경우는 다음과 같다. 수빈이는 1초 뒤에 +1, -1 번의 위치로 이동할 수 있다 수빈이는 0초 뒤에 현재위치 * 2 의 위치로 이동할 수 있다. 위의 조건대로 움직인 좌표를 Queue 에넣고 BFS를 사..
-
백준 2178 (미로 탐색)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 17:24
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N by M크기의 미로가 주어지며 시작점이 1 by 1 의 위치일 때 N by M 의 위치에 도달하기 까지 걸리는 최소 이동 횟수를 구하는 문제이다. #include #include #include using namespace std; struct Node{ int y, x; int cnt; }; int n, m; int checkY[4] = { 0, 0, 1, -1 }; int checkX[4] = { 1, -1, 0, 0 }..
-
백준 4963 (섬의 개수)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 17:07
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net M by N 크기의 격자판이 주어지며 이 격자판 안에는 육지와 바다가 있다. 육지는 상하 좌우 대각선 방향으로 이어질 수 있으며 이렇게 이어진 육지를 하나의 섬으로 본다. 이때 섬의 개수를 구하는 문제이다. 풀이 : BFS를 이용한 탐색 #include #include #include #include #include #include using namespace std; struct Node{ int y,..
-
백준 2667 (단지번호붙이기)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 15:58
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 해당 문제는 0과 1로 이루어진 격자판이 주어지며 해당 격자판의 1은 집을 의미하고 0은 빈 집을 의미한다. 이때 집들의 모임인 단지를 정하고 단지의 개수와 각 단지마다 포함 된 집의 개수를 오름차순으로 출력하는 문제이다. 단지는 상하좌우로 인접한 집들의 집합이다. 풀이 : 2 중 for를 사용하여 격자판을 모두탐색 하며 만약 처음 방문하는 집일 경우에 BFS를 통한 상하좌우 방향의 집 탐색을 진..
-
백준 11724 (연결 요소의 개수)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 21. 03:30
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 해당 문제는 N개의 정점과 M개의 간선들이 주어질 때 하나로 연결 된 요소들의 총 개수를 구하는 문제이다. 풀이 : for 문을 사용하여 N개의 정점을 BFS를 사용하여 탐색하며 탐색한 정점은 check 해주며 Check 되지 않은 정점이 있을 경우 해당 정점에서 다시 BFS를 사용하여 정점을 탐색하는 과정을 반복하면서 check되..
-
백준 1260 (DFS와 BFS)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 21. 03:10
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 해당 문제는 N개의 정점이 주어지면 해당 정점들의 간선의 정보가 주어지면 해당 정점들의 간선을 통해 연결 되어 있는 정점들을 DFS, BFS로 탐색을 하며 탐색되는 각 정점을 출력하는 문제이다. 이때 하나의 정점에 연결 된 간선이 여러개라면 숫자가 작은 정점을 방문하는 조건이 있다. 주의 사항 : 하나의 정점에 간선이 여러개일 경우 숫자가 작은 정점부터 방문해..
-
백준 13023(ABCDE)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 20. 21:48
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 해당 문제는 N명의 사람으로 구성 된 그룹이 있으며, 해당 그룹은 M개의 인원들이 친구 관계를 맺고 있다. 이때 아래와 같은 조건의 친구관계를 가지는 그룹일 경우 1 출력 아닐경우 0을 출력하는 문제이다. 주의 사항 : N명의 사람이 최대 2000 명이기 때문에 2000번을 탐색하기에는 시간초과가 발생한다. 따라서 Vector 에 n 번째 인원의 친구 정보만 push 하는 과정을 통해 오직 친구인 사람의 번호만 Vector 에 저장하도록 한다. #include #include using namespac..
-
백준 11723 ( 집합 )컴퓨터 공학 기초/알고리즘 (구현) 2020. 8. 20. 17:22
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 해당 문제는 주어지는 명령의 조건에 따라 처리해주면서 알맞게 출력만 해주는 문제이다. 이때 한가지 주의해야 할 점이 있는데 일반 cin, cout 사용시 시간초과가 발생함으로 printf 와 scanf 사용 혹은 ios_base::sync_with_stdio(false); cin.tie(NULL); 위의 구문을 사용하여 입출력을 사용한다. 풀이 : #include #include #include using namespace std;..