📚 알고리즘/탐색(BFS,DFS)
[백준 2146] 다리만들기_bfs(c++)
[문제] https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net [문제를 보자마자 든 생각] 보자마자 일단 bfs로 단지나누기를 해야겠다고 생각했다. 단지를 나눈 다음, 한 단지에서 이동하다가 다른단지를 만날때까지의 거리를 구한다음 그 거리의 최솟값을 구하면 될것이라고 생각했다. [문제풀이] 이중for문 돌면서 육지라면 좌표를 bfs(int x, int y)에 전달. bfs() 에서 너비탐색하면서 바다이면 true, 육지이면 false를 반환하게 함 ==>..
[백준 6593] 상범빌딩_bfs(c++)
1.문제 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 www.acmicpc.net 2. 접근방법 3차원적으로 생각해야됐던 문제 동,서,남,북,상,하 상범이가 6가지 방향으로 움직이도록 한다. 나머지는 일반적인 bfs랑 똑같이 하면됐던 문제!!(단, xyz인덱싱 꼭 주의) 3. 문제풀이 상범이의 위치와, 움직인 시간 카운팅을 큐에 담는다. 테스트케이스를 한번에 받는 문제이므로 bool배열이나 기타 다른것들 초기화 꼭 시켜주기!!!!!!! 방문체크해가면서 second를 반환시켜..
[백준 10026] 적록색약_bfs(c++)
1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 2. 접근법 굳이 3차원배열로 안풀어도 될거같은데 저번주에 3차원배열로 푸는거에 꽂혀서 3차원 배열로 풀어봤다.. 적록색약인사람과 아닌사람의 방문체크배열을 따로 만들면 됐지만 나는 그냥 3차원 배열로 했다. 이것도 구역의 갯수를 구하는 것이기때문에 모든 정점을 다 방문해야 될것이라고 판단. 영역의 각 넓이는 구하지 않아도 되므로 전역변수로 area_cnt를 두고 영역의 갯수를 카..
[백준 2583] 영역구하기_bfs(C++)
1.문제 https://www.acmicpc.net/problem/2583 2.접근방법 bfs로 영역을 나눠야 겠다고 바로 생각!(게리맨더링이랑 비슷하다고 생각했다) 탐색시작점이 따로 없으니, 어디서부터 시작할지 고민했음 첫번째 영역의 탐색이 끝나고 나면(이동하면서 막혀서 더이상 이동할 수 없을때 영역이 정해짐) , 다음영역으로 어떻게 시작점이 넘어가야하는지 좋은 방법이 떠오르지 않음 결국 모든 점을 방문할 수 밖에 없겠다는 결론이 내려짐 ㅠ 한 점에서 시작 -> 큐가 비워짐 -> 첫번째 영역이 구해짐 -> 벡터에 넣는다 결국 벡터의 사이즈는 영역의 갯수가 됨 영역들의 넓이는 벡터 for문 돌면서 출력하면 됨 3.문제풀이 입력으로 주어진 사각형(넓이부분 전체 다 )을 map을 1로 만들어준다.(bfs를 ..