Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- hash table
- CSV
- Vue.js
- GitHub
- 구현
- 모의SW역량테스트
- SWEA
- boj
- django
- BFS
- programmers
- Bruth Force
- 알고리듬
- Algorithm
- 코딩테스트
- JavaScript
- Linked list
- Back tracking
- 시뮬레이션
- Python
- Priority Queue
- Data Structure
- SQL
- DFS
- aws
- gpdb
- Trie
- 코테
- spring boot
- 알고리즘
Archives
- Today
- Total
hotamul의 개발 이야기
[Algorithm][C++] BOJ 14442 벽 부수고 이동하기 2 본문
myt-algorithm-practice/Samsung SW Certi Adv
[Algorithm][C++] BOJ 14442 벽 부수고 이동하기 2
hotamul 2021. 8. 29. 00:53url: https://www.acmicpc.net/problem/14442
14442번: 벽 부수고 이동하기 2
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
풀이 핵심
1. bool type의 방문 여부 확인 용 3차원 배열
2. queue 최대 크기 (1000 * 1000 * 10)
3. 다음 탐색 위치가 벽이면서 현재 벽을 부순 횟수가 K보다 작다면 다음과 같이 큐에 추가
if (map[nr][nc]) {
if (cur.wall < K) {
visited[nr][nc][cur.wall] = visited[nr][nc][cur.wall + 1] = true;
push(nr, nc, cur.wall + 1, cur.dist + 1);
}
}
코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAXN (1000)
int R, C, K;
int map[MAXN + 1][MAXN + 1];
bool visited[MAXN + 1][MAXN + 1][10 + 1];
struct INFO {
int r, c, wall, dist;
};
INFO q[MAXN * MAXN * 10];
int fr, re;
void push(int r, int c, int wall, int dist) {
q[re].r = r, q[re].c = c;
q[re].wall = wall;
q[re++].dist = dist;
}
INFO front() { return q[fr]; }
void pop() { fr++; }
int isEmpty() {
if (fr == re) return 1;
return 0;
}
int BFS() {
push(1, 1, 0, 1);
visited[1][1][0] = true;
while (!isEmpty()) {
INFO cur = front();
pop();
if (cur.r == R && cur.c == C) {
return cur.dist;
}
const int dr[] = { 1,-1,0,0 };
const int dc[] = { 0,0,1,-1 };
for (int dir = 0; dir < 4; dir++) {
int nr = cur.r + dr[dir];
int nc = cur.c + dc[dir];
if (nr < 1 || nr > R || nc < 1 || nc > C) continue;
if (visited[nr][nc][cur.wall]) continue;
if (map[nr][nc]) {
if (cur.wall < K) {
visited[nr][nc][cur.wall] = visited[nr][nc][cur.wall + 1] = true;
push(nr, nc, cur.wall + 1, cur.dist + 1);
}
}
else {
visited[nr][nc][cur.wall] = true;
push(nr, nc, cur.wall, cur.dist + 1);
}
}
}
return -1;
}
int main() {
scanf("%d %d %d", &R, &C, &K);
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
scanf("%1d", &map[i][j]);
}
}
printf("%d", BFS());
return 0;
}
아쉬운 점
메모리 크기가 너무 크므로 원형 큐 또는 STL을 사용했어야 했다.
STL 사용 법을 익혀야겠다.
'myt-algorithm-practice > Samsung SW Certi Adv' 카테고리의 다른 글
[Algorithm][C++] BOJ 4991 로봇 청소기 (0) | 2021.09.02 |
---|---|
[Algorithm][C++] BOJ 9376 탈옥 (0) | 2021.09.02 |
[Algorithm][C++] BOJ 5014 스타트링크 (0) | 2021.09.01 |
[Algorithm][C++] BOJ 16236 아기 상어 (0) | 2021.08.30 |
[Algorithm][C++] BOJ 16954 움직이는 미로 탈출 (0) | 2021.08.28 |
Comments