BFS

[프로그래머스 Lv.3] 경주로 건설 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이처음에 문제를 풀 때, 최소 거리가 최소 비용을 보장하지 않을 것으로 판단되어서 DFS로 풀이하였다. 하지만, 일부 테스트 케이스에서 시간 초과가 발생하여 다른 방법으로 풀이해야 했다. (풀이를 검색해 보니 DFS + 메모이제이션 방식으로 풀이할 수 있다고도 한다.)###### DFS 방식으로 풀이, 시간 초과로 인해 실패 ######def solution(board): dirs = [(1, 0, False), (-1, 0,..

[프로그래머스 Lv.2] 게임 맵 최단거리 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이2차원 지도에서 출발지로부터 목적지까지의 최단거리를 알아내는 작업이므로, 전형적인 BFS 문제라고 할 수 있다. 따라서 풀이 자체도 특히 어려운 부분 없이 출발지부터 BFS를 진행하여, 목적지에 도착할 때 몇 칸 움직인 상태인지를 출력하면 되기에 간단한 편이다. 다만, 주의해야 할 점은 목적지에 도달하지 못한 경우에는 -1을 출력해야 한다는 점이다. 처음에 필자는 목적지에 도달하지 못하는 조건을 생각할 때, 단순히 목적지의 왼쪽과 ..

[프로그래머스 Lv.3] 단어 변환 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이BFS를 사용한 풀이이다. 풀고 나니 원래 보통 BFS라고 할 때 사용하는 while과 deque를 사용한 구조로 풀이되진 않았으나.. 어찌 됐든 한 단계씩 진행되는 BFS 구조를 사용하여 문제 풀이를 진행했다. 문제에 적힌 대로 주어진 단어의 한 글자씩 변환하며, 변환된 단어가 words 배열에 있는지 체크하고, 또 동시에 이전에 이미 변환을 진행했던 단어가 아닌지 확인하였다. 확인을 통과한 새로운 단어들을 모아 새로운 단계에서..

[프로그래머스 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..