낭만 IT

Problem Solve/DFS & BFS → (18)건

[백준] 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..
Problem Solve/DFS & BFS 2020. 3. 21. 15:37

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

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

[백준] 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[다음위..
Problem Solve/DFS & BFS 2020. 3. 21. 01:01

[백준] 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
Problem Solve/DFS & BFS 2020. 3. 21. 00:04

[백준] 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..
Problem Solve/DFS & BFS 2020. 3. 20. 23:50

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

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

[백준] 7576번 토마토 (c)

출처 한국정보올림피아드 지역본선 2013 고등부 1번 문제 번호 백준 7576번 토마토 코드업 4781 : 토마토(고등) 힌트 배열에 토마토가 익는 날짜를 저장 풀이 이 문제 풀이의 핵심은 배열에 토마토가 익는 날짜를 저장한다는 것이다. 익은 토마토의 입력이 1로 들어오기 때문에 day배열에 저장될 숫자는 그 위치의 토마토가 익는 날 +1이 된다. 토마토의 위치를 나타낼 dot 구조체를 만들어주고 dot을 넣을 큐q를 만들어 준다. BFS이기 때문에 가장 먼저 갱신된 값이 날짜의 최소값이다. 따라서 check배열을 만들어 주지 않고 day배열을 check배열처럼 사용할 수 있다. BFS가 끝나고 day배열에 들어있는 최대값을 찾으면 된다. 만약 0이 남아 있다면 익지 않고 남아있는 토마토가 있는 것이기 ..
Problem Solve/DFS & BFS 2020. 3. 17. 23:59

[백준] 7596번 토마토 (C)

출처 한국정보올림피아드 지역본선 2013 초등부 3번 문제 번호 백준 7569 토마토 코드업 :4773 토마토 (초등) 알고리즘 3차원 BFS 힌트 배열에 토마토가 익는 날짜를 저장 문제 풀이 이 문제 풀이의 핵심은 배열에 토마토가 익는 날짜를 저장한다는 것이다. 익은 토마토의 입력이 1로 들어오기 때문에 day배열에 저장될 숫자는 그 위치의 토마토가 익는 날 +1이 된다. 토마토의 위치를 나타낼 dot 구조체를 만들어주고 dot을 넣을 큐q를 만들어 준다. 3차원이기 때문에 방향 배열의 크기는 6*3이 된다. BFS이기 때문에 가장 먼저 갱신된 값이 날짜의 최소값이다. 따라서 check배열을 만들어 주지 않고 day배열을 check배열처럼 사용할 수 있다. BFS가 끝나고 day배열에 들어있는 최대값을..
Problem Solve/DFS & BFS 2020. 3. 16. 18:17

[백준] 2468번 안전영역 (C)

출처 한국정보올림피아드 KOI 2010 초등부 2번 문제 번호 백준 : 4697 안전 영역 코드업 : 2468번 안전 영역 알고리즘 DFS, Flood Fill 풀이 수면의 높이를 0부터 100까지 올려가면서 구역의 개수를 세어준다.(cnt) 각 수면의 높이마다 ans를 최대 값으로 갱신해준다. 매 높이 마다 구역을 새로 세어야 하기 때문에 check배열을 매번 초기화 해주어야 한다. #include using namespace std; int in[100][100]; int check[100][100]; int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; int n; void fill(int a, int b){ check[a][b]=1; for(int i=0;i=n||nb>=n..
Problem Solve/DFS & BFS 2020. 3. 15. 23:52

[백준] 2615번 오목 (C)

출처 한국정보올림피아드 KOI 2003 초등부 1번 문제 번호 코드업 : 4023 : 오목 백준 : 2615 오목 알고리즘 DFS 풀이 기존의 DFS 방식에서 방향에 대한 정보만 추가하면 된다. 승자와 가장 왼쪽 바둑돌의 위치를 출력하는 것이 목적이기 때문에 DFS를 시작한 바둑돌이 가장 왼쪽 위에 있도록 해줘야 한다. 따라서 아래 표의 순서대로 탐색을 해준다. 1 4 7 2 5 8 3 6 9 이제 방향 배열을 잡아줘야 하는데 현재 원소의 왼쪽에 있는 데이터들과 왼쪽 위에 있는 데이터들은 이미 확인했으므로 확인할 필요가 없다. 시작한 바둑돌이 가장 왼쪽 위에 있도록 탐색하려고 하기 때문에 오른쪽에 있는 바둑돌들만 확인해 주면 된다. 이미 확인 이미 확인 이제 볼거 이미 확인 * 이제 볼거 이미 확인 이제..
Problem Solve/DFS & BFS 2020. 3. 14. 19:00
◀ 1 2 ▶

티스토리툴바