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 |
Tags
- 12761 돌다리
- 자바 디자인 패턴
- 몽고디비 렘
- http 개념
- 자바 디자인패턴
- 하둡
- 12761번 돌다리
- 도메인 주도 개발 시작하기
- MongoDB Realm
- 백준 12761
- 백준
- 정렬
- 백준 사이트
- String 함수
- ddd
- 고 배열
- golang
- 도메인 주도 개발
- http 완벽가이드
- hadoop
- 백준 파이썬
- flask
- go
- domain driven develop
- golang struct
- 자바
- 백준 12761번
- 파이썬
- 우분투
- 트리 순회
Archives
- Today
- Total
개발바닥
BOJ_14442 [ 벽 부수고 이동하기 2 ] 본문
반응형
문제
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
문제 해결 방법
이동하면서 벽을 얼만큼 부수고 이동했는지 방문 변수를 통해서 확인을 한다.
방문 변수를 3차원으로 선언 후 visited[벽 부순 횟수][y좌표][x좌표] 를 이용해서 접근하고
bfs로 문제를 풀면 쉽게 해결할 수 있다.
소스 코드 보기
https://github.com/jokerKwu/BOJ_Algorithm/blob/master/BFS/BOJ_14442.cpp
jokerKwu/BOJ_Algorithm
Contribute to jokerKwu/BOJ_Algorithm development by creating an account on GitHub.
github.com
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define MAX 1002
int N, M, K;
char board[MAX][MAX];
int visited[11][MAX][MAX];
int m_xy[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
typedef struct {
int c;
int x;
int y;
}Info;
int bfs() {
queue<Info> q;
q.push({ 0,0,0 });
visited[0][0][0] = 1;
while (!q.empty()) {
Info c_info = q.front();
//목적지에 도달했으므로
if (c_info.x == M - 1 && c_info.y == N-1) {
return visited[c_info.c][c_info.y][c_info.x];
}
q.pop();
for (int i = 0; i < 4; i++) {
Info n_info = { c_info.c,c_info.x + m_xy[i][0],c_info.y + m_xy[i][1] };
int n_move_cnt = visited[c_info.c][c_info.y][c_info.x] + 1;
if (n_info.x < 0 || n_info.y < 0 || n_info.x >= M || n_info.y >= N) continue;
//다음 좌표가 벽이 아닌 경우 방문을 안했거나 , 이동횟수가 더 작다면
if (board[n_info.y][n_info.x] == '0' && (visited[n_info.c][n_info.y][n_info.x]==0||visited[n_info.c][n_info.y][n_info.x]>n_move_cnt)) {
visited[n_info.c][n_info.y][n_info.x] = n_move_cnt;
q.push(n_info);
}
//다음 좌표가 벽인 경우 현재까지 부순 벽의 개수가 K 보다 작다면 부술수 있으니
else if (board[n_info.y][n_info.x] == '1'&& K > c_info.c) {
n_info.c = c_info.c + 1;//벽을 부수고 이동
if (visited[n_info.c][n_info.y][n_info.x] == 0 || visited[n_info.c][n_info.y][n_info.x] > n_move_cnt) {
visited[n_info.c][n_info.y][n_info.x] = n_move_cnt;
q.push(n_info);
}
}
}
}
return -1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
}
}
cout<<bfs()<<'\n';
return 0;
}
반응형
'[ Algorithm ] > [ BOJ ]' 카테고리의 다른 글
BOJ_15653 [ 구슬 탈출4 ] (0) | 2020.06.30 |
---|---|
BOJ_10942 [ 팰린드롬? ] (1) | 2020.06.09 |
BOJ_16935 [ 배열 돌리기 3 ] (0) | 2020.05.07 |
BOJ_17069 [ 파이프 옮기기2 ] (0) | 2020.05.07 |
BOJ_17828 [ 문자열 화폐 ] (0) | 2020.04.08 |
Comments