[백준 2667] 단지번호붙이기 [C]
풀이 단지별로 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..
2021. 8. 14.
[백준 2234] 성곽 [C]
풀이 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}, {..
2021. 8. 14.
[백준 7569] 토마토 [C]
풀이 "백준 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..
2021. 8. 13.
[백준 7576] 토마토 [C]
풀이 "백준 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++..
2021. 8. 13.
[백준 2178] 미로 탐색 [C]
풀이 (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..
2021. 8. 13.
