0과 1의 쉼터

풀이 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; ..

풀이 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..

풀이 1과, 2의 답은 방 마다 bfs를 사용해 탐색하면 쉽게 구할 수 있다. 3의 답은 방의 각 칸에서 모든 방향으로 벽을 부셔보고 bfs를 사용해 탐색하면 되는데, 매번 방문한 장소를 초기화해주고, 벽을 뚫었다가 탐색이 끝나면 다시 막아주어야 한다. 방향의 순서는 문제에 주어진대로 bit값의 shift연산과 관련이 있으므로 서, 북, 동, 남 순서대로 탐색했다. 소스코드 #include #include #include #define MAX 50 int n, m, graph[MAX][MAX], rear; bool visited[MAX][MAX]; typedef struct{ int x, y; }Point; Point queue[MAX*MAX], d[4] = {{0,-1}, {-1,0}, {0,1}, {..

풀이 "백준 7576, 토마토"에서 좌표축을 하나 추가해주면 된다. 소스코드 #include #define MAX 101 int box[MAX][MAX][MAX], M, N, H, rear; int dx[6] = {-1, 1}; int dy[6] = {0, 0, -1, 1}; int dz[6] = {0, 0, 0, 0, -1, 1}; typedef struct{ int x, y, z; }Queue; Queue q[MAX*MAX*MAX]; void push(int i, int j, int k){ q[rear].x = i; q[rear].y = j; q[rear++].z = k; } int bfs(int empty){ if (!empty) return 0; int x, y, z, px, py, pz, fro..

풀이 "백준 2178, 미로 탐색"과 풀이가 비슷하다. 단, 시작점이 여러개이다. 토마토의 여부를 입력받을 때, 익지않은 토마토의 개수와 익은 토마토의 개수를 미리 계산했다. 익지않은 토마토를 발견할 때마다 empty를 하나씩 감소하며, 탐색이 끝난 후 empty가 0보다 크면 모든 토마토가 익을 수 없는 상황이기 때문에 -1을 반환했다. #include #define MAX 1001 int box[MAX][MAX], M, N, rear; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; typedef struct{ int x, y; }Queue; Queue q[MAX*MAX]; void push(int i, int j){ q[rear].x = i; q[rear++..

풀이 (0, 0)부터 범위를 초과하지 않고, 이동할 수 있는 공간이고, 방문한적 없는 곳을 탐색하면 된다. 다음에 이동할 좌표 (tx, ty)를 구조체 q에 저장하고 front, rear을 이용해 탐색을 진행했다. 소스코드 #include #include bool visited[100][100]; int graph[100][100], d[100][100]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; typedef struct{ int x, y; }Queue; void bfs(int N, int M){ d[0][0] = visited[0][0] = 1; Queue q[N*M]; q[0].x = q[0].y = 0; int x, y, front = 0, rear..