백준/DFS BFS20

• 

  [백준 5014번 / C++ / BFS] 스타트 링크 BFS 를 활용한 문제가 은근 많다. 최근 코테에서도 BFS 를 활용해서 풀었던 기억이 난다. DFS/BFS 를 응용한 문제를 파악하고 바로 풀수 있게끔 충분히 연습하자. #접근방법 이 문제의 핵심은 서두에서 언급했듯이 BFS를 활용하는 것이다. 여기서 건물의 위아래로 왔다갔다하는 것이 조금 헷갈리면 건물을 오른쪽 방향으로 누웠다고 생각해보자. 그러면 크기가 f인 배열에 현재 위치 s 에서 오른쪽(up), 왼쪽(down) 으로만 갈 수 있는데 목적지 g 에 도착하면 끝난다. 바로 응용해보면 현재 위치를 담은 좌표를 queue에 담고 너비 우선탐색을 하는것이다. 즉, 왼쪽으로 갔을 때 좌표값과 오른쪽으로 갔을 때 좌표값을 queue담으면 된다. 그리고 방문처리를 해준다. 여기서 중요한 문제는 1. 왼쪽 좌.. 백준/DFS BFS 2022. 6. 28.

• 

  [백준 4179번 / C++] 불! bfs 를 이용해서 풀면 되는 문제이다. #접근방법 이 문제는 생각보다 예외사항이 많았다. 이 점들을 고려하지 못한채로 접근해서 수정작업이 좀 필요했다. 그래서 문제를 풀기 전에 지문을 꼼꼼히 읽고 접근해야할 습관이 필요하다고 뼈저리 느꼈던 문제이다. 이 문제를 요약하자면 불이 상하좌우로 먼저 퍼지고 나서 지훈이가 불을 피해서 지도의 끝에 도착하면 빠져나갈 수 있다. 그냥 전형적인 BFS() 문제인데 예외사항이 무엇인지 한번 살펴보자. J는 입력에서 하나만 주어진다. 문제를 보면 위의 문장 한줄이 나와있다. 여기서 유추를 했어야만 했다. 즉, "J는 입력에서 하나만 주어질 수 있다" 라는 말은 F는 입력에서 하나일 수도 있고 없을 수도 있고 두개 이상일 수도 있다는 뜻이다. 나는 처음 접근할 때 아무생각.. 백준/DFS BFS 2022. 4. 2.

• 

  [백준 7569번 / C++] 토마토 [백준 6593번 / C++ ] 상범 빌딩 BFS 문제이다 . 코드가 상당히 길다. #접근 방법 상범이가 빌딩에 갇히고 말았다. 왜 갇혔는지 모르겠다. 평범한 BFS 문제보다 조금 까다로운 문제이다. 왜냐하면 평소에 풀던 문제는 상하좌우만 baebalja.tistory.com 위의 문제와 상당히 비슷한 BFS문제이다. #접근방법 토마토 문제는 상하좌우만 고려할 것이 아니라 윗층과 아랫층을 검사해야한다. 즉, queue에다가 y와 x 그리고 layer까지 고려한 데이터 값을 함께 넣어준다. 그리고 map이 가로와 세로를 넘어갔을 때만 체크해주는 것이 아니라 layer의 높이까지 고려해야한다. 익지 않은 tomato 개수를 미리 저장을 해주고 bfs를 호출해서 현재 익은 토마토에서 주변에 안익은 토마토가 있.. 백준/DFS BFS 2022. 3. 22.

• 

  [백준 6593번 / C++ ] 상범 빌딩 BFS 문제이다 . 코드가 상당히 길다. #접근 방법 상범이가 빌딩에 갇히고 말았다. 왜 갇혔는지 모르겠다. 평범한 BFS 문제보다 조금 까다로운 문제이다. 왜냐하면 평소에 풀던 문제는 상하좌우만 살피면 되는데 이 문제는 윗층과 아랫층도 비교해줘야한다. 근데 그것 말고는 큰 차이가 없다. 단지, 층(layer)을 나타내는 값과 이동할 때 추가되는 누적시간을 저장하는 큐를 하나 더 생성했을 뿐이다. 일반적인 BFS문제와 동일하지만 층의 범위까지 고려해서 풀어보자. #include #include #include #include #include using namespace std; int l, m, n; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; vector.. 백준/DFS BFS 2022. 3. 21.

• 

  [백준 9934번 / C++] 완전 이진 트리 dfs 문제이다. * 중위 순회의 흐름 차순은 L - Root - R 순이다. #접근방법 답을 저장할 이차원 벡터와 데이터를 저장할 일차원 벡터 생성. 시작 포인터와 끝 포인터를 지정하여 그 중간점을 매개변수로 전달하여 왼쪽 자식 노드의 끝까지 들어간다. level 이 입력받은 깊이의 수와 동일하다면 return. 해당 레벨에 위치의 이차원벡터에 현재 담고있는 데이터의 값을 담아준다. 우측 자식 노드로 재귀함수를 호출한다. #include #include using namespace std; int n; vector v; void dfs(int s, int e, int level, vector& data) { if (level==n) return; int mid = (s + e) / 2; dfs(s, m.. 백준/DFS BFS 2022. 3. 17.

• 

  [백준 2573번 / C++] 빙산 이 문제는 bfs를 활용해서 풀면 된다. #접근방법 bfs를 적용한 문제를 얼마나 많이 풀어봤냐에 따라서 해당 문제가 쉽게 느껴질 수 있고 어렵게 느껴질 수 있을거라고 생각한다. 빙산의 크기 map에 담고 map크기 만큼 temp라는 이차원배열을 생성한다. ( 갱신된 내용 temp에 저장.) 빙산 주변에 인접한 0의 개수(바다) 만큼 map의 값에서 빼준 후 결과 값을 temp 에 넣어준다. temp 이차원 배열에는 갱신된 내용이 담겨져 있고 해당 데이터를 토대로 덩어리를 계산해준다. 즉, bfs를 호출한 개수가 덩어리 개수이다. ( bfs는 서로 인접한 데이터에 값이 있으면 퍼지면서 탐색 하기 때문) 덩어리의 개수가 2개 이상이 아니면 다시 2번부터 반복한다. #include #include #incl.. 백준/DFS BFS 2022. 3. 14.

• 

  [백준 16953번 / C++] A → B dfs 문제이다 #접근방법 현재 값 current 변수에서 1. 곱하기 2를 해서 dfs를 호출. 2. 곱하기 10을 한 후 +1 을 dfs로 호출 이 두가지 경우를 dfs 함수 안에 두고 current 값이 B와 동일하다면 cnt값이 큰 것을 고른다. 즉, 위의 조건에서 1번을 통해 B값을 도출할 수 있고 2번을 통해 B값을 도출할 수 있으니 재귀호출한 횟수를 세어주는 cnt값을 비교해서 작은 값을 answer값에 저장시켜준다. #include #include using namespace std; long long a, b; long long answer = 987654321; void dfs(long long cur, long long cnt) { if (cur == b) { answer = min(.. 백준/DFS BFS 2022. 3. 14.

• 

  [백준 11048번 / C++] 이동하기 dp와 dfs를 활용한 문제이다. 이와 비슷한 문제를 아래에 dp 카테고리에 추가한 적이 있어서 이번엔 dfs 카테고리에 집어넣겠다. = n || ny = m)continue; res=max(dfs(ny, nx)+map[y][x],res); } return res; } int main() { cin >> m >> n; for (int i = 0; i > map[i][j]; cost[i][j] = -1; } } cout 백준/DFS BFS 2022. 3. 10.

• 

  [백준 1261번 / C++] 알고스팟 dfs 문제이다 #접근방법 dp (벽을 뚫은 횟수)를 생성한다. (큰 값으로 초기화 ) dfs 함수를 호출하는데 벽을 만난다면 카운트 +1 을 해주고 아니라면 현재 카운트대로 함수 호출 만약, dp (벽을 뚫은횟수) 배열에 값이 현재 매개변수로 받아온 카운트 값보다 작다면 갱신해준다. 그게 아니라면 리턴 ex) 0 0 1 1 1 1 0 0 0 1 0 0 예제1) m[0][0] -> m[0][1] -> map[1][1] -> map[1][2] -> map[2][2] 일때 벽을 총 1번 뚫는다. 예제2) m[0][0] -> m[1][0] -> map[1][1] -> map[2][1] -> map[2][2] 일때 벽을 총 3번 뚫는다. 여기서 보면 현재 위치가 둘다 map[2][2] 이지만 뚫어왔던 벽의 개수.. 백준/DFS BFS 2022. 2. 23.

• 

  [백준 3055번 / C++] 탈출 bfs 문제이다. #접근방법 1. 고슴도치, 물, 비버의 굴 위치를 저장 후 bfs() 호출 (물과 고슴도치의 위치를 각각 queue에 push) 2. 먼저 물의 위치가 저장된 queue에서 물의 좌표값을 pop 하면서 물이 이동할 수 있는 인접한 구역에 물로 바꾼다. 3. 고슴도치의 위치에서 상하좌우로 갈수 있는 경우 dis라는 배열에 더해나간다. 4. 고슴도치가 더이상 갈 수 있는 길이 없을 때 또는 고슴도치가 비버의 굴 위치에 도달했을 때 리턴 해준다. #include #include #include #include #include using namespace std; int m, n, a_y, a_x; queue w; //물이 차있는 곳 queue q; //고슴도치가 이동할 수 있는 곳 vecto.. 백준/DFS BFS 2022. 2. 17.