Study hard

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 �� www.acmicpc.net [풀이] 각 노드를 시작점으로 하여 bfs를 돌려보고 각 노드에서 가장 먼 노드까지의 길이중 가장 긴 것을 출력한다. #include #include #include #include //max #include //memset using namespace std; struct Pos { int x, cnt; }; struct Weight { int x, weight;//이어진 노..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] dfs로 부모 노드를 찾는 문제였다. 입력에서 부모자식 관계를 알 수 없기 때문에 양방향으로 저장해주었다. 1부터 차례로 자식노드를 찾으면서 자식노드의 부모노드가 현재노드임을 저장해주었다. #include #include using namespace std; #define Max 100001 int N; int Parent[Max]; bool check[Max]; vectorTree[Max]; void input() { cin >> N; for (in..

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;//육지의 좌..