BFS

[프로그래머스 Lv.3] 네트워크 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이deque를 사용한 BFS로 문제를 풀이하였다. 일반적인 BFS 문제를 풀이하는 것처럼 visited라는 배열을 통해 네트워크를 구성할 노드의 방문 여부를 확인하여 전체 노드 순회를 완료하였을 때 몇 개의 네트워크를 생성할 수 있는지 확인하면 된다. from collections import dequedef solution(n, computers): answer = 0 ..

(C++) 백준 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는 Stack을, BFS는 Queue를 사용해서 풀력 형식에 맞게 그래프의 정점을 하나씩 순회하도록 구현하면 된다. #include #include #include #include using namespace std; vector gp[1002]; int visited[1002]; qu..

(C++) 백준 11724번 - 연결 요소의 개수

문제 링크 : 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 풀이 방향이 없는 그래프를 BFS 하여 풀이하였다. BFS를 사용하여 하나의 정점부터 차례대로 순회하면 이것들은 하나의 연결 요소가 된다. 그렇기에 출발점을 정점 하나하나로 두고, 방문했는지 여부를 사용하면 연결 요소의 수까지 파악할 수 있다. #include #include using namespace std; vect..

(C++) 백준 13549번 - 숨바꼭질 3

문제 링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 백준 1697번(숨바꼭질)과 상당히 유사한 문제이다. 비슷하게 풀이하되 시간이 들지 않는 2배 순간이동을 최우선으로 체크하고, 다음으로 - 연산, + 연산 순으로 BFS를 쓰면 된다. #include #include #include #define X first #define Y second using namespace std; int n,k; ..

(C++) 백준 7569번 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 토마토(백준 7576번)의 3차원 버전이다. 2차원과 동일하게 진행하되 체크를 6개의 방향으로 진행하도록 BFS를 구현하면 된다. #include #include #include using namespace std; int dx[6] = {1,0,0,-1,0,0}; int dy[6] = {0,1,0,0,-1,0}; int dz[6] = {0,0,1,0,0..

(C++) 백준 10026번 - 적록색약

문제 링크 : https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 백준 1926번 그림 문제와 거의 동일한 문제이다. BFS를 이용하여 풀이를 하였다. 색약이 아닌 사람들은 1926번에서 풀이한 그대로 하면 되고, 색약인 사람들의 경우에만 R과 G를 동일한 색인 것처럼 풀이하면 된다. //boj 10026 성공 #include #include #include #define X first #define Y second using name..

(C++) 백준 1697번 - 숨바꼭질

문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 응용한 문제로 실버 1 문제치곤 어렵지 않게 해결할 수 있다. 다만 조건에 수빈이와 동생이 같은 위치에 있을 순 없다는 말이 없으므로 같은 위치에 존재하면 그냥 0을 출력하고 종료할 수 있도록 해야 한다. #include #include #include #define X first #define Y second using namespace s..

(C++) 백준 4179번 - 불!

문제 링크 : https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 BFS를 응용한 문제로, 불에 대한 BFS와 지훈이에 대한 BFS를 동시에 사용하는 방법으로 풀이하면 된다. 골드 4 문제답게 조건들을 설정하는 것이 매우 복잡했다. #include #include #include #define X first #define Y second using namespace std; int dx[4] = {1,0,-1,0}; int d..

(C++) 백준 7576번 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 BFS를 이용한 거리 문제와 비슷하게 풀이하면 된다. 거리를 토마토가 익는 데 걸리는 시간의 길이라고 생각하고 풀면 어렵지 않게 해결할 수 있다. 문제 해결 시 중요한 점은 시작점이 될 수 있는 후보들, 즉 익은 토마토들의 위치를 먼저 파악 후에 이들을 Queue에 넣고 시작해야 한다는 점이다. #include #include #include #define X ..

(C++) 백준 2178번 - 미로 탐색

문제 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 BFS를 사용하여 풀이하였다. 다른 BFS 문제를 풀어보았다면 실버 1 문제라기엔 크게 어렵지 않은 문제이다. 오히려 공백없이 들어오는 숫자들을 어떻게 한 자리씩 입력받아 저장할지를 더 많이 고민하였다. #include #include #include #define X first #define Y second using namespace std; int dx[4] = {1,0,-1,0}; int dy[4] =..