본문 바로가기
반응형

Queue10

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 2383 : 점심 식사시간 (모의 SW 역량테스트) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 점심 식사시간 시뮬레이션 문제는 그대로 잘 구현하면 된다. 먼저 좌표를 저장할 RC 구조체를 선언한다. people배열에는 사람의 좌표를, stair 배열에는 계단의 좌표를 저장한다. list는 DFS로 사람을 나눌 때 사용한다. 2차원 배열 distance는 계단과 사람 사이의 거리이다. distance[1][3]은 1번 계단과 3번 사람과의 사이를 의미한다. stairLength는 계단을 내려가 이동이 완료되는 시간을 저장한다. (1/2번 계단에 대한 시간) #define MAX (10 + 5) int T, N; int MAP[MAX][MAX]; int list[MAX]; typedef struct st { int r; int c; }RC; RC pe.. 2021. 5. 7.
BOJ 7569 : 토마토 (3차원) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/7569 BOJ 7576 토마토는 2차원에서 토마토가 퍼져나갔다. 이번 문제는 3차원에서 토마토를 만들어가면 된다. 2차원에서는 4방향으로 토마토를 큐에 담았지만, 3차원에서는 좌표의 높이(h)에 대해 위, 아래 토마토를 추가해주면 된다. 즉, 총 6방향으로 BFS가 퍼져 나간다. /* 순서대로 왼쪽, 위, 오른쪽, 아래 */ int dr[] = { 0, -1, 0, 1 }; int dc[] = { -1, 0, 1, 0 }; void BFS() { for (int h = 1; h 2021. 3. 17.
BOJ 7576 : 토마토 알고리즘 문제 전체 링크 www.acmicpc.net/problem/7576 미로 탐색 문제에서 BFS를 이용하여 거리를 계산하였다. 같은 방법을 토마토 문제에서 적용할 수 있다. 토마토를 모두 넣고 미로 탐색과 같은 방식으로 BFS를 적용하면, 토마토가 상자를 꽉 채우게 된다. 토마토가 상자를 꽉 채우는 것은. 각 토마토가 상자에서 최소로 가능 경로를 모든 토마토에 대해 실행하면 된다. 다음과 같은 5 x 5 상자(MAP)에 토마토가 있다고 가정하자. 편의상(경계 조건을 신경쓰지 않기 위해) MAP의 주변은 -1로 만든다. 이제 모든 토마토를 queue에 담는다. 참고로 토마토 문제의 경우는 미로 탐색과는 달리 visit이 필요가 없다. 상자 자체를 visit으로 같이 사용할 수 있기 때문이다. 즉, .. 2021. 3. 16.
BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제 알고리즘 문제 전체 링크 www.acmicpc.net/problem/11866 www.acmicpc.net/problem/1158 참고 - BOJ 10845, 18258 : 큐, 큐2 - BOJ 1168 : 요세푸스 문제 2 요세푸스 문제 0은 요세푸스 문제보다 K, N 값만 다르다. MAX 값을 5000이상으로 잡으면 두 문제 모두 풀 수 있다. 큐 기본 문제를 풀면 큐의 구현은 아래와 같다. 큐의 크기 : wp - rp 큐의 pop : queue[rp++] 큐의 push : queue[wp++] 먼저 사람들을 큐의 순서대로 넣는다. 예제의 경우는 1 2 3 4 5 6 7 이 큐에 들어간다. K 번째 사람을 제거하기 위해 K - 1번 pop하고 다시 push한다. 이 경우는 K = 3 - 1 = 2번 .. 2021. 3. 13.
BOJ 16236 : 아기 상어 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16236 아기 상어 구조체는 좌표와 몇 마리의 물고리를 먹었는지, 그리고 현재의 크기가 필요하다. typedef struct st1 { int r; int c; int eat; int size; }SHARK; SHARK babyshark; input을 받으면서 9인 경우에 아기 상어 구조체를 초기화 해주자. void input() { scanf("%d", &N); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { scanf("%d", &MAP[r][c]); if (MAP[r][c] == 9) { MAP[r.. 2021. 3. 6.
BOJ 2178 : 미로 탐색 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2178 BFS를 이용하여 MAP에 거리를 남길 수 있다. 이 문제의 경우는 벽이 0, 길이 1이므로, 1인 경우에 큐에 담고, visit을 체크한다. 다음과 같은 미로가 있다고 가정하자. 우리가 최종적으로 구해야할 지도의 모습은 아래와 같다. 도착점부터 칸을 세기 때문에 (1, 1)에서 (5, 5)까지 이동해야하는 칸은 총 9칸이다. 이제 BFS를 이용하여 거리를 재보자. 2차원 MAP 탐색의 기본은 단지번호붙이기와 비슷하다. 지금의 경우는 큐에서 pop할 때마다, 현재 위치 + 1을 기록하면 된다. ※ BFS 탐색 과정은 유니티를 이용해서 확인할 수 있다. 먼저 최초 시작점 (1, 1)을 queue에 담고, visit[1][1] = .. 2021. 3. 5.
BOJ 2667 : 단지번호붙이기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2667 2차원 배열의 구역을 BFS, queue를 이용해 나눠보자. 집인 곳을 발견하면, 집 주변의 영역을 찾아야 한다. BFS를 이용해 푸는 방법은 다음과 같다. 1) 집이 아니면(0) 넘어간다. 2) (r, c)가 집이면 queue에 담고 visit[r][c] = 1 로 체크한다. (다음에 다시 담지 않게 하기 위해) 3) (r, c)의 4방향이 집이고 visit이 0이면 queue에 담는다. 이때, queue에 담으면서 집의 개수(영역의 크기)를 센다. 4) 최종 영역의 개수를 return 한다. 5) 2) ~ 3)을 queue가 빌 때까지 한다. ※ BFS 탐색 과정은 유니티를 이용해서 확인할 수 있다. 실제로 그림으로 확인해보.. 2021. 2. 27.
반응형

티스토리툴바