본문 바로가기
반응형

BFS23

유니티 - BFS를 이용하여 평면을 그리드로 나누기 (Converting a Plane to a Grid with BFS) Unity 전체 링크 아래와 같이 평면을 그리드로 분할해보자. BFS(Breadth First Search)는 너비 우선 탐색으로 길 찾기에 주로 쓰이는 알고리즘이다. 이번 경우에는 Plane에서 갈 수 있는 경로를 탐색하여 Grid로 표시하기 위해 BFS를 사용한다. 자세한 알고리즘 설명은 아래 링크를 참고하자. - BOJ 2178 : 미로 탐색 - BOJ 2667 : 단지번호붙이기 아래의 영상은 BFS를 이용하여 (0, 0, 0) 좌표에서 Plane을 탐색한 결과다. 먼저 구현하기 쉽게 (0, 0, 0)에는 반드시 Plane이 있다고 가정하자. 여기서 Plane은 Tag = "Plane"인 경우를 말한다. (0, 0, 0)에 반드시 Plane이 있다고 가정하고 이 점을 중심으로 그리드를 만든다. 원하.. 2022. 7. 16.
BOJ 23289 : 온풍기 안녕! (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) https://www.acmicpc.net/problem/23289 좌표에 맞춰서 상하좌우 define과 dr, dc 배열을 정의한다. #define RIGHT (1) #define LEFT (2) #define UP (3) #define DOWN (4) /* 순서대로 오른쪽 : 1, 왼쪽 : 2, 위 : 3, 아래 : 4 */ int dr[] = { 0, 0, 0, -1, 1 }; int dc[] = { 0, 1, -1, 0, 0 }; 문제를 풀기 위한 구조체를 정의한다. RC = 온도를 체크해야하는 checkPoint의 좌표 (r, c) HEATER = 온풍기의 좌표 및 방향 관리 QUEUE = 바람을.. 2021. 11. 6.
BOJ 23288 : 주사위 굴리기 2 (삼성 SW TEST 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 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 알고리즘 문제 전체 링크 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 < K인 경우로 변경하고 visit[0]을 visit[out.k]로 visit[1]을 visit[out.k + 1]로 변경한다. if (out.k < K) /* k < K일 때, */ { /* queue의 다음 좌표가 0이고 visit[out.k]도 0 */ if (MAP[nr][nc] == 0 &&.. 2021. 6. 2.
BOJ 2206 : 벽 부수고 이동하기 알고리즘 문제 전체 링크 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로 시작하게 된다. 보통 다음 좌표가 벽이 있는 경우, queue에 넣지 않지만, visit[0]에서 넘어온 queue의.. 2021. 5. 30.
SWEA 1953 : 탈주범 검거 (모의 SW 역량테스트) 삼성 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 2021. 5. 20.
반응형

티스토리툴바