목록백준/bfs, dfs (47)
Study hard
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net [풀이] Tree[][2]배열에 각 노드의 왼쪽 자식 노드 번호와 오른쪽 자식 노드 번호를 저장하였다. #include using namespace std; int N; char Tree[27][2];//[x][0]:x의 왼쪽 자식, [x][1]:x의 오른쪽 자식 void input() { cin >> N; for (int i = 0; i < N; i++) { char a, b, c; cin..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] bfs알고리즘을 이용하여 풀었다. visited배열에 해당 칸이 출발지로부터 몇번째 칸인지 저장하면서 반복문을 돌리고, 목적지인 (N,M)에 도착하면 bfs함수에서 빠져나오면 된다. 이때 visited[N][M]이 (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소의 칸 수이다. #include #include #include //scanf using namespace std; struct Pos {..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net [풀이] bfs알고리즘을 이용하여 풀었다. riped배열에 해당 좌표의 토마토가 보관 후 며칠이 지났을 때 익었는지 저장했다. 만약 다른 익은 토마토로부터 영향을 받았을 때가 더 빠른 일수라면 그걸로 바꿔줬다. #include #include #include //memset #include //max using namespace std; struct Tomato { int x, ..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net [풀이] 간단한 bfs알고리즘으로 풀었다. 한 번 bfs를 할 때 방문하지 않은 사각형에 대해 위,아래,왼쪽,오른쪽,대각선으로 연결되어 있는 사각형을 조사하여 한 개의 섬을 모두 조사할 때까지 탐색하였다. bfs를 돌린 횟수가 섬의 개수가 된다. #include #include #include //memset using namespace std; struct Island { int x, y;//육지의 좌..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net [풀이] bfs탐색을 사용하여 풀었다. 그림처럼 단지마다 1,2,3 표시할 필요는 없고, 각 좌표의 상하좌우를 탐색해 이어져 있는 1의 개수를 구하면 된다. #include #include #include //sort #include //scanf using namespace std; struct Pos { int x, y;//Map의 x좌표, y좌표 }; int N; int Map[26][26]..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net [풀이] dfs를 이용하여 풀었다. 다음 학생이 처음 방문하는 학생이면 check[학생번호]를 true로 바꾸어주고, 이미 한 번 방문했던 학생을 다시 방문하게 된다면 Recheck[학생번호]가 false일 경우 거쳐왔던 학생만큼 cnt에 저장한다. (cnt는 프로젝트 팀에 속한 학생들의 수이다) ※dfs마지막에 Recheck[현재 학생번호]를 true로 바꿔줘야 같은 싸이클을 그 싸이클에 속하는 원소..