백준/DFS BFS20

• 

  [백준 13549번 / C++] 숨바꼭질 3 bfs를 문제를 활용해서 풀면 된다. #접근방법 1. 방문 배열 100001개 생성 후 큰 값으로 초기화 2. 수빈이의 현재 위치 queue에 push. 3. queue에 들어간 수빈이의 현재 위치에서 갈 수 있는 경로는 현재 값에서 -1 , +1, *2 이다 현재 위치에서 3가지 방향의 값을 연산하여 해당 인덱스의 visited값을 갱신해간다. 4. queue에 값이 있을 동안 반복문을 돌리며 수빈의 위치와 동생의 위치가 동일하다면 해당 인덱스의 visitied값을 출력하고 종료한다. #include #include #include #include #include using namespace std; int n, k; int visited[100001]; queue q; void bfs() { int .. 백준/DFS BFS 2022. 2. 17.

• 

  [백준 17144 / C++] 미세먼지 안녕! 살짝 노가다 문제이긴 한데 한번 풀어보면 괜찮은 문제이다. 1. map 에서 미세먼지의 수치가 저장되어 있는 좌표값들을 모두 큐에 넣는다. 2. 큐에 있는 좌표값들을 꺼집어 내서 상하좌우에 해당하는 규칙에 따라 값을 갱신한다. 3. 갱신한 맵을 공기청정기를 중심으로 공기가 정화되게끔 map의 원소값을 시계 방향, 반시계 방향으로 이동시킨다. 4. time이 입력한 값이 되면 맵의 모든 미세먼지 값을 더해서 출력해준다. #include #include #include #include #include using namespace std; queue q; int map[50][50]; int map_sum[50][50]; int m, n, time; int dy[4] = { 0,0,-1,1 }; int dx[.. 백준/DFS BFS 2022. 2. 15.

• 

  [백준 12851번 / C++] 숨바꼭질 2 bfs를 활용해서 풀면된다. 1. 수빈이와 동생의 위치가 처음부터 같을 경우 바로 결과값 출력 2. 그렇지 않다면 수빈이의 x좌표값과 시간을 queue 넣고 bfs 호출 3. 1초당 수빈이가 갈 수 있는 경우의 수는 총 3가지 이므로 방문하지 않거나 범위를 넘어서진 않는다면 queue에 push하고 bfs 호출 4. 만약 수빈이의 위치가 처음으로 동생의 위치에 도달했을 때 시간 저장 5. 같은 시간대에 도착한 경우가 여러개인 경우 result2 의 값을 증가 #include #include #include #include #include using namespace std; queueq; int n, k; int visited[100001]; int result1, result2; void bfs() {.. 백준/DFS BFS 2022. 2. 10.

• 

  [백준 2636번 / C++] 치즈 1. 사각형의 테두리는 0으로 되어있다. 2. {0,0}에서 bfs를 돌린다. 3. {ny,nx} 좌표를 가지고 있는 map의 값이 1이라면 벽이라고 생각을 하고 뚫고 가진 못하지만 방문 처리만 해주자. 4. 상,하,좌,우로 연결된 길을 모두 탐색했다면 visited에 1로 기록되어있는 map을 0으로 갱신하자. (즉, 벽을 허물라) 5. map에서 갱신 된 내용이 없으면 리턴하고 그렇지 않다면 다시 {0,0}에서 bfs를 돌린다. #include #include #include #include using namespace std; queueq; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int map[100][100]; int visited[100][1.. 백준/DFS BFS 2022. 1. 27.

• 

  [백준 2667번 / C++] 단지번호붙이기 bfs, dfs 자신있는 것으로 해보자. main문에서 함수 호출할 때 증가하는 cnt는 영역을 표현. 함수에서 또 함수를 호출할 때 증가하는 cnt는 영역안의 넓이를 표현. #include #include #include #include using namespace std; int n; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int map[25][25]; int visited[25][25]; int cnt1; void dfs(int y, int x) { cnt1++; for (int i = 0; i = n || ny < 0 |.. 백준/DFS BFS 2022. 1. 24.

• 

  [백준 10026번 / C++] 적록색약 bfs 문제로 풀면 쉽게 나온다. 1. map 에 RGB 색상에 맞게 숫자로 저장. (그대로 해도 상관없음. 저는 보통 숫자로 합니다.) 2. 반복문을 돌면서 해당 위치가 방문되지 않았다면 bfs() 함수를 호출 한다. 3. bfs 기본적인 알고리즘을 사용해 동일한 색상에 인접한 구간들을 다 방문 처리한다. 4. 메인문에서 bfs 호출된 개수를 출력 ( 첫번째 답안 ) 5. map 에서 R과 G를 동일한 번호로 저장. 6. 2~4 번과 동일. #include #include #include #include #include #include using namespace std; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int n; int map[100][1.. 백준/DFS BFS 2022. 1. 24.

• [백준 1260번 / C++] DFS와 BFS dfs와 bfs의 원리를 터득하기 위해 올린다. 그렇게 어렵지 않은 문제이니 평소에 dfs나 bfs가 애매한 감이 있다면 풀어보길 권한다. #include #include using namespace std; int map[1001][1001]; int visited1[1001]; int visited2[1001]; int n, m, v; queue q; void bfs() { while (!q.empty()) { int v = q.front(); cout v; for (int i = 0; i > a >> b; map[a][b]=1; map[b][a]=1; } visited2[v] = 1; dfs(v); cout 백준/DFS BFS 2022. 1. 20.

• 

  [백준 7576 / C++] 토마토 bfs를 활용해서 풀면 되는 문제이다. 지금까지 풀어왔던 bfs와는 조금 다른 점이 있었다. 익은 토마토가 하나일 수도 있고 두개일 수도 있고 즉, 여러개일 수도 있다. 다시말해, 여러 영역에서 익은 토마토들이 존재하면 동시에 움직이면서 visited를 세팅 해야한다는 것이다. 주인공이 하나가 아니라는 뜻이다. 익은 토마토들을 먼저 다 queue에 넣어줘서 bfs를 시작하게 된다. 먼저 queue에 넣은 익은 토마토들의 x,y 좌표값을 vector에 넣어주고 vector에 들어있는 각 좌표값의 상, 하, 좌, 우 를 모두 살펴보고 갈 수 있는 길이 있다면 그 값들을 모두 다시 큐에 넣어준다. 그러한 작업이 모두 이루어지고 나면 그때, cnt값을 하나 올려주는 것이다. #include #include #i.. 백준/DFS BFS 2022. 1. 20.

• 

  [백준 2178번 / C++] 미로 탐색 해당 문제를 bfs() 를 활용해서 풀었다. bfs나 dfs 를 어느정도 활용 할 줄 아시는 분이라면 쉽게 풀수 있을 것이다. 항상 (1,1) 에서 출발하여 해당 지점부터 map 의 1로 저장되어 있는 부분을 지나가면서 map 의 끝지점까지의 거리를 살펴보면 된다. 첫 시작점부터 map 값이 1인 자리를 visited 배열을 활용해 거리를 갱신해 나간다. 다음 그림을 보면서 어떤식으로 visited가 갱신되는지 확인해보자 그림은 백준 첫 예제를 토대로 그린 것이다. #include #include #include #include #include using namespace std; int map[101][101]; int visited[101][101]; int dx[4] = { -1,0,1,0 }; i.. 백준/DFS BFS 2022. 1. 17.

• 

  [백준 2468번 / C++] 안전 영역 DFS를 활용한 문제이다. N은 2이상 100이하이며 각 지역의 높이는 1이상 100이하 인것을 알아두자. 먼저 지역의 높이를 나타내는 map을 입력 받고 check라는 배열도 h값이 변할 때마다 생성해주자. 각 지역은 1부터 100이하이니 비가 차오른 높이도 그렇게 생각할 수 있지만 비가 아예 안 올 경우도 생각 해야한다. 그러니, h의 범위는 0부터 100이라는 것을 주의하자. 해당 그림을 보면서 어떻게 구현을 하였는지 확인하고 코드 주석을 보면서 이해해보자. #include #include #include using namespace std; int map[100][100], check[100][100], n; int answer = INT_MIN; int dx[4] = { 0,0,1,-1 }; i.. 백준/DFS BFS 2022. 1. 14.