trudy

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 색종이 만들기 https://xoxoxoxox.tistory.com/61 와 쿼드트리 문제 https://xoxoxoxox.tistory.com/171와 매우 유사한 문제였다. 쿼드 트리 문제와 다르게 이차원 배열이 공백으로 구분지어서 입력이 주어졌기 때문에 StringTokenizer을 이용해서 토큰을 구분해주는 작업이 필요했다. BufferedReader br = new Buffer..

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 높이는 n (사용자가 입력한 값) 가로는 2n -1 따라서 [n][2n-1] 크기의 char 형태의 배열을 선언하고 출력했다. package backjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class bj_2448 { static char[][] map; private static void drawSta..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이해하기 유기농배추(https://xoxoxoxox.tistory.com/118), 단지 번호 붙이기 문제(https://xoxoxoxox.tistory.com/125)와 유사했던 문제였다. 이 문제의 특이점은 대각선에 있는 것도 연결된 걸로 본다는 것이었다. 또, 테스트 케이스가 여러 개 주어져 while문으로 반복해서 입력을 받아야 했고, 매번 map[][]과 visited[][]를 초기..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이해하기 문제점 1 : 입력 받기 유기농 배추 문제랑 매우 유사했던 문제였다. (풀이 https://xoxoxoxox.tistory.com/118 ) -- [백준 1012번 C++] 유기농 배추 1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보..

11725번: 트리의 부모 찾기 (acmicpc.net) 11725번: 트리의 부모 찾기루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.www.acmicpc.net 이해하기 루트가 없는 트리가 주어졌는 데, 트리의 루트를 1이라고 정한다. (??????) 일단 이해한 바로는 각 노드의 부모를 구해야하니 루트가 1로 주어졌으니까 1부터 dfs를 진행시켜서 노드들의 부모를 찾으면 된다. 주어진 간선들이 순서가 없으므로 무방향 그래프로 간주하고 풀어야한다. 이 특징들만 적용해서 일반 dfs 문제처럼 풀었더니 쉽게 풀 수 있었다. 최종 코드#include #include using namespace std; int n; int visited[..

1991번: 트리 순회 (acmicpc.net) 1991번: 트리 순회첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파www.acmicpc.net이해하기 트리 순회 3가지전위 순회 (preorder) : 현재 노드 - 왼쪽 노드 - 오른쪽 노드 중위 순회 (inorder) : 왼쪽 노드 - 현재 노드 - 오른쪽 노드 후위 순회 (postorder) : 왼쪽 노드 - 오른쪽 노드 - 현재 노드 위 3가지 트리 순회는 해당하는 순서대로 함수로 재귀적으로 호출해 구현할 수 있다. [백준] 1991번 : 트리 순회 [C/C++] — 백준 하루 한 문제 (ti..

1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이해하기 이번 문제에서는 배추가 재배하는 땅이 행렬로 주어졌기 때문에 탐색을 인접 행렬로 해야하는 걸 쉽게 알 수 있었다. 배추가 심어져 있는 사이클 혹은 연결 요소의 개수를 구하는 문제이므로 탐색의 횟수를 구하면 된다. 또 가로 길이와 세로 길이가 다를 수 있다는 점을 고려해야 하면서 문제의 난이도가 다른 탐색 문제들에 비해서 올라갔다. 인접행렬 DFS 코드 void DFS(int v){ //현재 노드 방문 visited[..

2606번: 바이러스 (acmicpc.net) 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 이해하기 탐색 문제는 문제를 읽으면 탐색으로 풀어야하는지 다른 유형의 문제들보다 티가 나는 거 같다. 또, 엄청난 응용이 있다기 보다는 DFS나 BFS를 어떤 구현방법(인접 행렬, 인접 리스트)을 적절히 사용하는 지가 포인트가 되는 것 같다. 탐색에서 체크해야할 부분은 가장 처음 방향 그래프, 무방향 그래를 구분해야한다. 이번 문제에서는 무방향 그래프로, 1번 노드가 속한 사이클에 총 몇 개의 노드가 있는지 구해야했다. ..

10451번: 순열 사이클 (acmicpc.net) 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 이해하기 바로 전 문제였던 [백준 11724번 - 연결요소의 개수]와 거의 동일하다. 다른 점이 있다면 방향이 있는 간선들로, 사이클의 개수를 구해야한다. 또, 테스트 케이스가 주어져서 여러 번 반복해야했다. 코드는 거의 비슷한데 테스트 케이스를 위한 반복문과 배열/벡터 초기화 코드가 추가 되었고 순열을 저장할때 v[i].push_back(..

11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 저번 dfs, bfs 문제는 인접행렬을 통해서 했었는데, 인접 리스트가 더 좋은 것 같아서 이번에는 벡터를 이용한 인접 리스트를 이용해서 풀어볼 것이다! 벡터를 이용한 인접 리스트 한 노드에서 인접한 정점들을 모두 벡터로 연결시킨다. vector v[node개수+1]; v[시작 노드].push_back(인접한 노드); vector v[4]; v..