# BFS
백준 14502, 연구소 - Brute Force & Backtracking, BFS
https://www.acmicpc.net/problem/145021) 추가할 벽 3개 위치 선택 => Backtracking2) 추가할 벽 3개 위치 선택 후, 입력 행렬을 0, 0 ~ n, m 차례로 확인바이러스 칸(2)이고 아직 방문 안한 경우, BFS
DFS/BFS
DFS(Depth-First Search) 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로서 스택 자료구조(혹은 재귀함수)를 이용한다. 구체적인 동작 과정 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리 2) 스택의 최상단 노드
백준 12851, 숨바꼭질 2 - BFS
https://www.acmicpc.net/problem/12851BFS 로 최소 시간 갱신해가면서 탐색탐색 종료 조건=> 목표 지점(동생)까지 도달한 최소 시간 < 현재 위치까지 도달한 최소 시간다음 탐색 지점 추가 1) 다음 후보 지점이 범위 안에 있
[프로그래머스] 경주로 건설
1-1. 정답 코드 1-2. 오답 코드 2. 후기 그동안 BFS 문제를 풀 때, 큐에 좌표를 저장하는 일은 많았지만, 좌표의 현재 좌표값까지 같이 저장한 경우는 없었다. 그도 그럴 것이 popleft()로 꺼낸 좌표(=(x,y))를 이용하면 graphx값을 얻을
[BOJ] 16928. 뱀과 사다리 게임 - c++
https://www.acmicpc.net/problem/16928100칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값=>(queue)사용 BFSC++풀이int mve102 = 뱀/사다리로 이동하는 구간 정보 저장(기본값으로 해당 위치)
백준 10026, 적록색약 - DFS / BFS
https://www.acmicpc.net/problem/10026본 문제는 단순히 탐색하는 영역의 수를 찾는 문제이므로, BFS가 더 쉬움입력 행렬을 0, 0 ~ n, n 차례로 확인=> 아직 방문 안했으면 BFS 탐색 시작=> Queue에 탐색 시작 좌표
[백준] 2178 미로탐색 (파이썬)
N×M크기의 배열로 표현되는 미로가 있다.1 0 1 1 1 11 0 1 0 1 01 0 1 0 1 11 1 1 0 1 1미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)
[백준] 18주차 스터디 (18352 특정 거리의 도시 찾기, 14502 연구소, 14888 연산자 끼워넣기)
18352 특정 거리의 도시 찾기 📌문제 링크 https://www.acmicpc.net/problem/18352 💡 문제 풀이 한 도시에서 다른 도시들로 가는 최단거리를 구하는 거니까 다익스트라 알고리즘을 사용하면 되겠다고 생각했다 ....... 근데 이번 주
[백준] 18352번 - 특정 거리의 도시 찾기
문제 18352번 아이디어 큐를 사용하여 방문처리(True,False)를 해나가면 된다. 소스코드 >뭐가 틀렸는지 모르겠다....... => 해결!!!!!! 시작노드 방문처리를 안해줌... 최종코드
[알고리즘] BFS(너비우선탐색), DFS(깊이우선탐색) 2
깊이우선탐색, 인접노드를 stack 자료구조에 넣는다는 것이 핵심.탐색노드를 stack에 넣은 후 추출하여 방문처리한다.이후 해당 탐색노드의 인접노드 중 방문하지 않은 노드만 stack에 넣는다.stack에 넣은 노드를 추출하여 방문처리, 그 노드의 인접노드 중 방문하
[백준/파이썬/BFS,DFS]18주차 문제풀이 (#18352, #14502, #18405, #14888)
깊은 부분을 우선적으로 탐색 -> 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 도랑가 다른 경로로 탐색하는 알고리즘스택 자료구조에 기초 (재귀 함수로 간결하게 구현 가능)가까운 부분을 우선적으로 탐색큐 자료구조에 기초일반적으로
DFS,BFS - 예제
이코테 149p 제한1초 / 128MB입력얼음틀 세로길이 N, M (1<=N, M<=1,000)2줄~N+1줄까지 얼음틀 형태 주어짐 (0=구멍, 1=그렇지 않음)출력한번에 만들 수 있는 아이스크림의 갯수 출력예시N \* M 크기의 얼음 틀이 있다.구멍이 뚫린
DFS/BFS - 이론정리
그래프 이론 을 참고하자!그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘1\. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.2\. 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으
백준 2468, 안전 영역 - Brute Force, DFS / BFS
https://www.acmicpc.net/problem/2468행렬 입력하면서, 최대 지역 높이 저장브루트 포스로 가능한 비의 양 모두 확인=> DFS 반복=> 비의 양: 0 이상 최대 건물 높이 미만(비의 양 == 0 인 경우, 모든 지역이 안전 영역 =>
백준 16953, A → B - BFS
https://www.acmicpc.net/problem/16953BFS => Queue에서 이전 값을 꺼내서 2가지 연산 수행 1) 연산 결과 값 == B 이면, 탐색 성공 2) 연산 결과 값 < B 이면, Queue 에 추가 3) 연산 결과 값 > B
백준 - 2636번 치즈
https://www.acmicpc.net/problem/2636오랜만에 감 다시 잡아야해서 살짝 쉬운문제로 꺼냈다기본적인 BFS로 풀었다1\. 치즈가 모두 녹았는지 체크해서 모두 0이면, 반복문 종료1-1. checkZero로 그냥 배열 탐색해서 0이 아니면
[프로그래머스] 타겟 넘버 - Python
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 1, 1, 1, 1, 1로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변
최단경로(c++) 백준 1504번
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번