0과 1의 쉼터

풀이 배추흰지렁이는 인접한 배추(기준이 되는 배추로부터 상하좌우에 위치한 배추)로 퍼져나갈 수 있다. 따라서 인접한 배추들을 전부 탐색하고, visited에 탐색한 배추를 기록하고자 한다. 결국 인접한 배추들의 덩어리인 연결 요소(Connected Component)의 개수를 구하는 문제이다. 배추가 위치한 장소만을 탐색하기 위해 배추의 위치를 입력받을 때 배추의 위치를 location에 기록한 후, DFS의 시행횟수를 세어 풀이했다. 소스코드 소스코드 보기 출처 및 참고자료 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net

풀이 n명에 대해서 각각 dfs을 해 만들어진 팀의 학생 수 만큼 전체에서 빼면 된다. 중복을 방지하기 위해, 팀을 짜기 시작한 경우(visited[0])와 탐색이 끝난 경우(visited[1])로 확인을 해주었다. 이전에 만난적 없는 번호이면 짝을 찾아가고, 만난적 있는 짝일 때, 그 짝의 탐색이 끝나지 않은 경우라면 순환이 가능한 즉 팀이 만들어 질 수 있다. 순환점을 발견하기 전 까지 재 탐색을 하며 개수를 세주고, 마지막에 자기 자신을 세어 주면 된다. 소스코드 #include #include #include #define MAX 100001 bool visited[2][MAX]; int arr[MAX], N, cnt; void dfs(int num, int depth){ if (!depth){ ..

풀이 입력된 대문자 알파벳의 아스키코드 값을 이용해, 한 번이라도 방문한 적 없는 경우에만 탐색해 최대의 칸 수를 구하면 된다. 소스코드 #include #include char arr[20][20]; bool visited[26]; int R, C, result; int dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1}; void BT(int x, int y, int cnt){ cnt > result && (result = cnt); for (int i = 0; i = 0 && ny >= 0 && nx < R && ny < C){ int idx = arr[nx][ny] - 65; if ..

풀이 8자리수의 소수를 확인하기 위해 1e8만큼의 공간을 할당하면 메모리 제한에 막힌다. 심지어 조건에 맞는 모든 소수의 개수가 100개도 안된다. 때문에, 다음과 같은 규칙을 찾아 문제를 해결했다. N의 자릿수는 2, 3, 5, 7 이어야 한다. 2를 제외한 모든 짝수는 소수가 아니기 때문에 홀수만 탐색해야 한다. 소스코드 #include #include int prime(int num){ int sq = sqrt(num); for (int i = 2; i

풀이 네 자리 수를 하나씩 바꾼 수가 소수이면서, 중복을 피하기 위해 기존에 확인한 수가 아닌 경우에만, Queue에 담아주고, 자리수를 바꾸기 전의 수의 변환 횟수에 1을 더한 값을 자리수를 바꾼 후 숫자의 변환 횟수에 입력해주었다. 소스코드 #include #include #include #include #define MAX 10000 bool cNum[MAX]; int cnt[MAX], queue[MAX]; void bfs(int old, int pw){ int front = -1, rear = -1, n; cnt[queue[++rear] = old] = 0; while (front < rear){ if ((n = queue[++front]) == pw) return; for (int i = 0; ..

풀이 건물 W를 완성하기 위해서는 건물 1에서 건물 W로 향하는 건물들이 완성되어야 하기 때문에, W값에서 역으로 DFS방식을 사용했다. W에서 1로 향하는 건물들이 모두 건설되어야 하기 때문에 D값이 가장 큰 값을 time에 넣어주어 반환해야 한다. 좀더 효율적인 탐색을 위해 총 time을 check에 넣는 memoization방식으로 해결했다. 단, D값은 0이상이기 때문에 -1로 초기화해서 사용해야 한다. 소스코드 #include #include #include #define max(a, b) a > b ? a : b int D[1001], N, check[1001]; bool O[1001][1001]; int construction(int c){ if (check[c] != -1) return c..

풀이 Queue에 연산값과 최솟값을 저장해주어, 연산값이 B가 될 때까지 탐색해주는 방식으로 풀이했다. 처음으로 들어오는 값이 1e8일 경우 10을 곱해주면 int의 범위를 벗어나므로 num은 long long으로 담아주었다. 만약 연산이 불가능하다면, num == B 조건을 만족하지 못하고 모든 Queue가 비었다는 것이므로, -1을 출력하면 된다. 소스코드 #include #include using namespace std; void bfs(int A, int B){ queue q; q.push(make_pair(A, 1)); while (!q.empty()){ long long num = q.front().first; int cnt = q.front().second; q.pop(); if (num ..

풀이 조건에 맞게 값을 넣어줄 수 있는 Binary Search Tree를 구현하는 문제이다. 소스코드 #include #include typedef struct node{ int data; struct node *left, *right; }*pNode; void postorder(pNode root){ if (root == NULL) return; postorder(root->left); postorder(root->right); printf("%d\n", root->data); } pNode make_tree(pNode root, int data){ if (root == NULL){ root = (pNode)malloc(sizeof(pNode)); root->data = data; root->left..

풀이 시간 제한이 있어 dfs로 이미 탐색한 영역에는 이동할 수 있는 칸의 수의 최댓값을 dp에 기록하는 방식으로 풀이했다. 소스코드 #include #define max(a,b) a > b ? a : b #define MAX 500 int forest[MAX][MAX], n; int dp[MAX][MAX]; int dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1}; int dfs(int x, int y){ if (!dp[x][y]){ dp[x][y] = 1; for (int i = 0; i = 0 && ty >= 0 && tx < n && ty < n) if (forest[tx][ty]..

풀이 단지별로 bfs를 사용해 탐색하고, 방문한 곳을 0으로 만들어주었다. 단지내 집의 수를 main으로 반환해 complex에 담아주었고, Quick Sort로 정렬 후 출력해주었다. 소스코드 #include #include #define MAX 25 typedef struct{ int x, y; }Point; Point queue[MAX*MAX]; int graph[MAX][MAX], rear, N; int dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1}; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void push(int i, int j){ queue[rear].x = i; queue[rea..