0과 1의 쉼터

풀이 단지별로 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}, {..

풀이 X를 비트로 표현했을 때 1의 개수가 필요한 막대의 개수와 일치한다. 소스코드 #include int main(){ int X, cnt = 0; scanf("%d", &X); do{ if (X & 1) cnt++; } while (X >>= 1); printf("%d", cnt); } 출처 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net

풀이 비트연산자를 이용해 풀이하는 문제이다. all은 반복문을 돌릴필요없이 2^21에서 1을 빼면 20칸의 비트가 모두 1이 된다. 소스코드 #include #include int main(){ int M, S = 0, num; char op[7]; scanf("%d", &M); while (M--){ scanf("%s", op); if (!strcmp(op, "all")) S = (1

풀이 map을 사용해 간단히 풀이했다. 소스코드 #include #include #include using namespace std; int main(){ cin.tie(NULL); ios_base :: sync_with_stdio(0); int N, M; cin >> N >> M; map info; string site, pw; while (N--){ cin >> site >> pw; info[site] = pw; } while (M--){ cin >> site; cout

풀이 "백준 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..

풀이 위의 예제는 다음과 같은 규칙이 있다. gcd(1, 소수) = 1 이므로 계산할 필요가 없으며, gcd(소수, 소수) = 소수 이다. gcd(N, M) = K일 때, gcd(N + K*i, M + K*i)는 모두 K이다. (단, i = 2~N or M) 위의 조건에서 얻은 K는 K의 제곱수가 존재할 경우 변경된다. N과 M크기를 이용해 K의 개수를 구할 수 있다. 두번째 조건에서 얻은 K들의 곱들과 세번째 조건에서 얻은 수의 중복을 피해야 한다. 다음과 같이 p+K*i (단, i = 0 ~ (p+K*i

풀이 "백준 11689, GCD(n, k) = 1"를 이용해 풀이했다. 시간초과는 발생하지 않으니 그냥 0을 입력받을 때까지 반복하면된다. 소스코드 #include int main(){ long long n; while (1){ scanf("%lld", &n); if (!n) break; long long euler = n; for (long long p = 2; p*p