본문 바로가기

Algorithm/BFS

 (64)
(C++) - 백준(BOJ) 2206번 : 벽 부수고 이동하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 정의하기 : 필요한 정보는 (i,j)의 맵에 도착했을 때 벽의 상태 w(0이면 부수지 않음, 1이면 부서짐) 입니다. 따라서 2차원을 두 가지로 나눠서 생각해야하므로 3차원의 visited배열을 이용해 거리와, 벽의 상태, 방문여부를 확인할 수 있도록 저장합니다. 2. bfs함수 시행 : 두 가지 방식으로 시행됩니다. 2-1. 이동할 수 있는 곳이라면 ..
(C++) - 백준(BOJ) 1963번 : 소수경로 www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net bfs로 푼 문제였습니다. 풀이방법 1. 에라토스테네스의 체를 이용해 9999까지의 소수를 모두 구합니다. primt[index]이 0이라면 index는 소수입니다. 2. bfs 시행 : 체크가 안되어 있고 소수인 모든 수를 queue에 push합니다. push할 때는 원래 소수경로의 거리 + 1을 다음 수의 check배열에 저장해줍니다. string으로 수를 변환하면 코드를 더 깔끔하게 할 수 있습니다. 이 후 한 번..
(C++) - 백준(BOJ) 12886번 : 돌 그룹 www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net bfs로 푼 문제였습니다. 풀이방법 1. 두 그룹씩 선택하는 방식이 6가지입니다. 2. 이 6가지에 대해 bfs를 수행하면 됩니다. Code #include using namespace std; int ck[2001][2001]; int bfs(int a,int b, int c){ queue q; q.push({a,b,c}); ck[a][b] = 1; ck[b][a] = 1; ck[a][c] = 1; ck[..
(C++) - 백준(BOJ) 16953번 : A → B www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net bfs 문제였습니다. 풀이방법 1. 원하는 수 b에 도착했을 때 지나온 길을 세주기 위해 queue를 pair로 선언합니다. 이 때 int 범위를 *10 + 1 연산을 하거나 *2를 했을 때 초과할 수 있으므로 long long자료형으로 선언하도록 합니다. 2. bfs를 실행합니다. 매번 pop을 하여 횟수와 값을 봅니다. x*2 b; cout
(C++) - 백준(BOJ) 1926번 : 그림 www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net bfs문제였습니다. 풀이방법 인접한 그림들은 모두 그림 하나의 일부입니다. 방문하지 않은 곳, 그림이 칠해져있는(1인) 곳에 대해 bfs를 실행합니다. 이 때, bfs가 호출되는 수가 곧 영역의 개수가 됩니다. 또한 bfs함수가 호출된 후 실행시 한 영역에 대해 1의 개수를 센 후 반환합니다. 이 때 반환값이 곧 한 영역의 그림 넓이가 됩니다. Code #include using namespace std; using..
(C++) - 백준(BOJ) 3184번 : 양 www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net bfs문제였습니다. 풀이방법 1. 처음 양, 늑대 마리 수 세기 : 입력 받은 후 각자 마리 수를 세줍니다. 2. 울타리가 아닌 부분에 대해 bfs실행 : 한 영역이란 울타리('#')로 둘러쌓인 부분입니다. 이 영역에 대해 늑대와 양의 수를 세줍니다. 만약 늑대가 양보다 많다면 해당 영역의 양의 수만큼 기존에 셌었던 양의 수에서 빼줍니다. 반대의 경우에는 늑대를 제거해줍니다. 3. 답 출력 Code..
(C++) - 백준(BOJ) 1303번 : 전쟁 - 전투 www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net bfs기본 문제였습니다. 풀이방법 1. 설계 : W병사의 영역, B병사의 영역을 구해 각자 더한 후 출력합니다. 2. bfs실행 : queue를 시용합니다. 방문하지 않은 곳이 만약 같은 병사가 위치한 곳이라면 방문한 뒤 해당 병사의 명 수를 ++해줍니다. 그 후 그 부분을 다시방문해 다음 병사를 살펴봐야 하므로 해당 위치를 push 해줍니다. 영역의 크기를 다 셌다면 영역 넓이 * 영..
(C++) - 백준(BOJ) 5567번 : 결혼식 www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net bfs를 이용하여 푼 문제였습니다. 풀이방법 1. 입접행렬을 만들어줍니다. a, b가 친구라면 b,a도 친구입니다. 양방향 그래프로 push_back으로 해야합니다. 2. 상근이를 start node로 해 bfs를 시행합니다. visited배열을 선언합니다. 이는 i번째 노드의 level이 저장되어 있고 이는 방문했는지의 여부 또한 볼 수 있는 2가지의 용도입니다. 방문하지 않은 노드가 있으면 해당 노드를 방문..

티스토리툴바