분류 전체보기(97)
-
[백준/C++] 5014번 스타트링크
문제: www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제풀이 일차원 직선에서의 최단거리를 구하는 문제이다. BFS 알고리즘으로 문제를 풀었다. 코드 #include #include using namespace std; int dist[1000001]; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int f,s,g,u,d; cin>>f>>s>>g>>u>>d; queue q; q.push(s); dist[s] = 1..
2021.04.01 -
[백준/C++] 2573번 빙산
문제: www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제풀이 BFS로 주변 바다 블록의 개수를 세어서 바다 블록의 수만큼 현재 높이에서 뺀 후 board에 갱신하는 방식으로 문제를 풀었다. 처음 풀 땐 빙하의 최대 높이가 10이기 때문에 10년안에 모든 빙하가 녹을 것이라고 생각해서 1~10년을 brute-force 했었다. 하지만 다음 그림과 같은 반례가 있기 때문에 빙하가 녹는 기간은 10년을 훌쩍 넘을 수 있다. 때문에 빙하가 두 덩이가 되거나..
2021.03.31 -
[백준/C++] 5427번 불
문제: www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 문제풀이 BFS를 이용해 최단거리를 구하는 문제이다. 불과 상근이의 시작점을 큐에 넣어 BFS 하면 상근이는 먼저 붙어있는 불을 피해 이동할 수 있게 된다. 이때 상근이를 큐의 마지막에 넣어야 불과 상근이가 같은 장소로 동시에 이동하는 일이 없다. 코드 #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,..
2021.03.31 -
[백준/C++] 10026번 적록색약
문제: www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제풀이 BFS 알고리즘 문제이다. 큐와 방문여부배열, 영역개수를 2개씩 선언하여 하나는 색약이 아닌 사람 다른 하나는 색약인 사람의 영역 개수를 구하였다. 코드 #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int visited1[100][100] = {0..
2021.03.30 -
[백준/C++] 2468번 안전 영역
문제: www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제풀이 브루트포스와 BFS 알고리즘을 이용하여 문제를 풀었다. 비의 높이(h)에 대하여 h보다 높이가 높은 지대의 인접한 땅들의 영역 개수를 BFS로 구한다. 이때 h가 0부터 100일 때까지의 경우의 수 모두 비교한다. 코드 #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int board[100][1..
2021.03.30 -
[백준/C++] 2667번 단지번호붙이기
문제: www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제풀이 각 영역의 넓이를 구하여 오름차순으로 출력하는 문제이다. BFS를 이용하여 각 구역에 대하여 탐색하고 그 넓이를 각각 벡터에 저장하였다. 벡터를 sort() 함수를 이용해 오름차순 정렬시킨 후 출력하였다. 코드 #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; ..
2021.03.29