[백준] 1260번 DFS와 BFS (C++)

문제 주소 백준 1260번 DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 DFS, BFS 풀이 간단한 DFS와 BFS 구현 문제이다. DFS는 재귀함수와 스택으로 구현할 수 있고, BFS는 q로 구현해야 한다. DFS를 하고 check배열을 초기화 해주어 BFS를 한다. #include #include using namespace std; int graph[1001][1001]; int check[1001]; int n, m; void dfs(i..

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 21.
• textsms

[백준] 2206번 벽 부수고 이동하기 (C++)

문제 주소 백준 2206번 벽 부수고 이동하기 알고리즘 BFS 힌트 어떤 위치에 온 상태가 벽을 부수고 온 것인지, 벽을 부수지 않고 온 것인지 구분 해야 한다. 풀이 위치(a, b)와 상태(w : 벽을 부쉈다면 1 부수지 않았다면 0)를 원소로 가지는 dot구조체를 만들어 준다. check배열도 위치와 상태를 담을 수 있도록 3차원으로 선언 해 준다. 현재의 위치가 목표 위치라면 ans를 출력하고 main 함수를 종료 해 준다.q를 다 확인 할 때까지 목표점에 도착하지 못하였다면 목표점에 도달할 수 없는 것이므로 -1을 출력해준다. 벽이 있고 벽을 뚫지 않았다면 q에 넣어주고 벽이 없다면 check배열을 하여 중복되지 않도록 q에 넣어준다. #include #include using namespace ..

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 21.
• textsms

[백준] 1697번 숨바꼭질 (C++)

출처 USACO US Open 2007 Contest Silver 2번 문제 주소 백준 1697번 숨바꼭질 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 알고리즘 BFS 힌트 check 배열(방문 배열)에 그곳에 가게 되는 시간 + 1을 저장한다. 풀이 수빈이가 이동할 수 있는 위치는 3군데가 있다. 각 각의 위치가 주어진 범위를 벗어나지 않는 지 확인을 한 후 왔던 곳인지 확인을 한다. 처음 위치를 1로 하고 (이는 check배열의 본질을 잃지 않기 위함이다.) check[다음위..

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 21.
• textsms

[백준] 2178번 미로 탐색 (C++)

문제 주소 백준 2178번 미로 탐색 알고리즘 BFS 힌트 BFS를 하자. 풀이 BFS의 가장 기초적인 문제이다. 문제에서 미로 탈출이 가능한 입력만 주어진다고 했다. 1이면 갈 수 있고 0이면 갈 수 없기 때문에 1이고 check가 되어 있지 않는 곳만 탐색을 해주면 된다. #include #include using namespace std; typedef struct dot{ int a, b; }; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int in[101][101]; int check[101][101]; queue q; int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=1;i

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 21.
• textsms

[백준] 1023번 유기농 배추 (C)

문제 주소 백준 1012번: 유기농 배추 알고리즘 DFS, Flood Fill 힌트 Flood Fill 알고리즘을 사용하여 구역의 개수를 구한다. 풀이 배추들의 위치를 입력받기 전에 in배열과 check배열을 초기화 해주어야 한다. check가 되어 있지 않으면서 배추가 있는 곳을 탐색하여 주변 배추들이 있는 곳을 check한다. #include using namespace std; int n,m; int in[50][50]; int check[50][50]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; void fill(int a, int b){ check[a][b]=1; for(int i=0;i=n || nb>=m||nax; for(int q=0;q>m>>n>>c; f..

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 20.
• textsms

[백준] 2485번 키 순서 (C)

출처 한국정보올림피아드 지역본선 2011 초등부 4번 문제 번호 백준 2458번 키 순서 코드업 4714 : 키 순서 알고리즘 DFS 힌트 나보다 큰 아이보다 작은 아이와의 관계는 알 수 없음 나보다 큰 아이보다 큰 아이는 나보다 큼 나보다 작은 아이보다 작은 아이는 나보다 작음 나보다 작은 아이보다 큰 아이와의 관계는 알 수 없음 풀이 들어오는 입력들을 그래프에 저장해 줄 때 1과 2로 구분하여 저장해줌으로써 누가 더 큰 아이인지 구분이 가능하게 해준다. 나보다 큰 아이들과 나보다 작은 아이들의 합이 전체 아이의 수 - 1 (n-1) 이라면 모든 나의 등 수를 알고있다고 할 수 있다. 따라서 dfs함수를 구현 할 때 몇 번째 아이에 대해 탐색할건지 n와 어느 방향에 대해(큰 아이들, 작은 아이들) 탐색..

• format_list_bulleted Problem Solve/DFS & BFS
• · 2020. 3. 20.
• textsms