본문 바로가기

Algorithm/BFS

 (63)
(C++) - 프로그래머스(2017 카카오 코드 예선) : 카카오프렌즈 컬러링북 programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr BFS를 이용해 풀었던 문제였습니다. 풀이방법 1. visit하지 않은 영역마다 영역의 개수를 증가 2. visit하지 않은 영역마다 bfs함수 실행, 영역의 크기를 반환 Code #include #include #include #include #include using namespace std; int visit[101][101]; int dx[4] = {0,0,1,-1}; i..
(C++) - 백준(BOJ) 2638번 : 치즈 답 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net bfs를 이용해 치즈가 모두 녹는 시간을 출력하는 문제였습니다. 풀이방법 1. 가장자리에 치즈를 놓는 경우는 없으므로 (0, 0)은 무조건 외부공기에 해당합니다. 이를 시작점으로 bfs를 진행합니다. 2-1. bfs함수 안에서 인접한 상하좌우 칸이 공기(0)라면, check해준 후 air queue에 넣어줍니다. 2-2. 인접한 칸이 치즈(1)라면, cheese queue에 무조건 넣어줍니다. 이를 통..
(C++) - 백준(BOJ) 2589번 : 보물섬 답 www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net bfs를 이용해 한 대륙에서 타일과 타일사이의 최대거리를 구하는 문제였습니다. 풀이방법 : 육지가 나올 때마다 bfs로 최대거리를 구한 후 갱신합니다. Code #include #include #include using namespace std; int n, m, ans; int d[51][51]; int ck[51][51]; char map[51][51]; int dx[] = {0,0,1,-1}; int dy[]..
(C++) - 백준(BOJ) 11866번 : 다리만들기 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이방법 : 섬마다 땅에 번호를 매긴 후 BFS를 이용해 원래섬에서 다른 섬까지의 거리의 최솟값을 구하면 답이됩니다. Code : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 ..
(C++) - 백준(BOJ) 1260번 : DFS와 BFS 답 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 기본적인 DFS와 BFS를 구현하는 문제였습니다. 풀이방법 : DFS : 정점 i에서 시작하여 그와 연결된 정점을 또다른 시작점으로 하는 재귀함수로 구현하였습니다. BFS : 정점 i에서 시작하여 그와 연결된 모든 정점을 그 노드 번호가 낮은 노드를 최우선순위로 탐방하도록 queue를 이용하여 작성하였습니다. 1 2 3 4 5 6 7 8 9 10 11 12 1..
(C++) - 백준(BOJ) 16985번 : Maaaaaaaaaze https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다. www.acmicpc.net BFS와 순열구현 문제였습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 6..
(C++) - 백준(BOJ) 18809번 : Gaaaaaaaaaarden https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양 www.acmicpc.net BFS와 백트래킹을 이용해 푼 문제였습니다. 12345678910111213141516171819202122232..
(C++) - 백준(BOJ) 2573번 : 빙산 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net bfs로 푼 문제였습니다. 풀이방법 1. bfs로 빙산 영역의 개수를 구할 수 있습니다. 빙산 영역의 개수가 1개 인동안 계속 년도를 증가시키면서 확인합니다. 2. loop를 도는 동안 얼음을 bfs로 녹입니다. 얼음이 있다면 근처 인접한 바다 영역의 개수를 구하고 기존 얼음이 있는 부분에서 바다 영역의 개수를 빼줍니다. 원본에서 미리 빼준다면 바다 영역의 개수를 정확히 구할 수 없기 때문에 copyBoa..

티스토리툴바