본문 바로가기

Algorithm/BFS

 (64)
(C++) - 프로그래머스(고득점 kit - (DFS/BFS)) : 네트워크 답 programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr bfs문제였습니다. 풀이방법 1. bfs의 호출 개수가 곧 네트워크의 개수가 됩니다. 2. 연결된 인접행렬의 정점을 계속 q에 push하면서 ck배열로 방문했음을 체크해줍니다. Code #include using namespace std; void bfs(int x, int ck[], vector &computers){ queue q; q.push(x); ck[x] = ..
(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..

티스토리툴바