본문 바로가기
반응형

BFS39

BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) https://www.acmicpc.net/problem/23288 input은 아래처럼 처리한다. BOJ 14499 : 주사위 굴리기는 (0, 0) 부터 시작하였으나 여기서는 (1, 1)부터 시작한다.#define MAX (20 + 5)int N, M, K;int MAP[MAX][MAX];void input(){ scanf("%d %d %d", &N, &M, &K); for (int r = 1; r  BOJ 14499 : 주사위 굴리기를 참고하여 주사위를 아래와 같이 정의한다.typedef struct st1{ int up; int le.. 2021. 10. 25.
BOJ 2252 : 줄 세우기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2252 A가 학생 B 앞에 서야 한다는 조건이 있으므로 위상 정렬을 이용하여 풀면 된다. 즉, A → B에 대해 B의 indegree가 1 증가하고, indegree가 0인 학생부터 BFS를 시작하면 된다. 설명은 BOJ 1005 : ACM Craft와 동일하다. #include int N, M, A, B; int indegree[32100]; int queue[100100]; int rp, wp; typedef struct st { int value; struct st *next; }NODE; NODE HEAD[32100]; NODE POOL[100100]; int pcnt; void Make(int p, int c) .. 2021. 7. 17.
BOJ 1005 : ACM Craft 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1005 위 그림에서 2번, 3번 건물은 1번 건물이 완료되어야 건설을 시작할 수 있다. 4번 건물은 2번, 3번 건물이 완료되어야 건설을 시작할 수 있다. 따라서 각 node에 들어오는 화살표 (in-degree)가 작은 순서대로 건설이 시작된다. 이런 문제는 위상 정렬을 이용해서 풀 수 있다. 1번의 경우에는 들어오는 화살표가 없으므로 in-degree가 0이다. 2, 3번의 경우는 in-degree가 1이며, 4번은 2가 된다. 입력받을 변수와 in-degree를 저장할 배열, 그리고 건설 시간을 저장할 배열, 답을 저장할 배열을 선언한다. ans[node] = 해당 node 건물이 완료될 때 까지 걸린 시간이다. #.. 2021. 7. 14.
BOJ 5465 : 곰돌이 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5465 queue에는 좌표 (r, c)와 depth(곰이 움직인 거리)를 담을 수 있도록 구조체를 아래와 같이 선언한다. typedef struct st { int r; int c; int depth; }QUEUE; QUEUE queue[MAX * MAX]; int wp, rp; 주어지는 input의 알파벳은 숫자로 변경한다. 그리고 곰돌이의 최초 위치와 도착해야하는 집의 좌표는 따로 (sr, sc), (er, ec)에 저장한다. void input() { int change['Z' + 1] = { 0 }; change['T'] = -1; /* 나무 */ change['G'] = 0; /* 빈 칸 */ change['H'.. 2021. 6. 12.
BOJ 14442 : 벽 부수고 이동하기 2 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/14442  BOJ 2206 : 벽 부수고 이동하기에서 벽을 K번 부술 수 있도록 코드를 수정하면 된다. 최대 10번까지 부술 수 있으므로 visit 배열을 10개 이상으로 만든다.//int visit[2][MAX][MAX];int visit[10 + 2][MAX][MAX]; BFS에서 out.k == 0인 경우를 out.k visit[0]을 visit[out.k]로 visit[1]을 visit[out.k + 1]로 변경한다.if (out.k  최종 코드는 아래와 같다.#include #define MAX (1000 + 10)int N, M, K;int MAP.. 2021. 6. 2.
BOJ 2206 : 벽 부수고 이동하기 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2206  BOJ 2178 : 미로 탐색에서 BFS를 이용하여 길찾기 문제를 해결할 수 있었다.벽 부수고 이동하기의 경우는 벽 1개를 부술 경우 최단 거리가 달라지기 때문에 난이도가 약간 더 높다. 먼저 방문 여부를 위해 visit 배열을 사용한다.이 때, visit[0][MAX][MAX]는 벽을 0번 부순 visit 배열이고,visit[1][MAX][MAX]는 벽을 1번 부순 visit 배열로 가정한다. 아래의 미로에서 (1, 1)부터 미로를 탐색한다고 가정해보자.visit[0]의 (1, 1)은 1로 시작하게 된다. 보통 다음 좌표가 벽이 있는 경우, q.. 2021. 5. 30.
SWEA 1953 : 탈주범 검거 (모의 SW 역량테스트) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 탈주범 검거 링크  (1, 1)부터 MAP을 입력받는다. 또한 tc 초기화를 위해 0 ~ N + 1을 먼저 0으로 만들어준다.좌표 저장을 위해 RC 구조체를 선언한다.int T, N, M, R, C, L;int MAP[MAX][MAX];int visit[MAX][MAX];typedef struct st2{ int r; int c;}RC;RC queue[MAX*MAX];int rp, wp;void input(){ scanf("%d %d %d %d %d", &N, &M, &R, &C, &L); for (int r = 0; r  파이프 7종에 대해 정의하기 위해 아래의 구조체를 만든다.type.. 2021. 5. 20.
BOJ 17472 : 다리 만들기 2 (A형 상시) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17472  아래의 순서대로 구현한다. 1) BFS를 이용해 섬을 구분한다.2) 섬과 섬 사이의 거리를 구한다.3) 섬의 개수 N에 대해, 다리 N - 1개를 선택하여 모두 연결되어 있다면, 다리의 길이를 갱신한다.구조체는 좌표를 기억하기 위한 RC 구조체가 필요하다.MAP 주변은 모두 -1로 처리하고 (1, 1)부터 입력을 받는다.connect 배열은 섬과 섬 사이의 거리를 저장하기 위한 배열이다.섬과 섬 사이의 거리는 가장 가까운 거리만 필요하므로, 큰 값(WORST = 0x7fff000.. 2021. 5. 1.
BOJ 17471 : 게리맨더링 (A형 상시) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17471 A형에서 그래프는 2차원 배열로 만들면 대부분 충분하다. 제시된 N이 매우 작기 때문이다.(N이 매우 큰 그래프는 링크드 리스트를 이용해 그래프를 만들어야 한다.) 만약 1번 구역과 2번 구역이 인접하다면, MAP[1][2] = MAP[2][1] = 1, 그렇지 않다면 0이 된다.people 배열에는 구역의 인구 수를 저장한다.#define MAX (10 + 5)int N;int MAP[MAX][MAX];int people[MAX];void input(){ scanf("%d", &N).. 2021. 4. 28.
반응형

티스토리툴바