18513번: 샘터
첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤
www.acmicpc.net
<풀이>
일단 평소 처럼 체크배열 쓰려다가 범위가 제대로 안정해져있어서 set을 사용했다.
-> 조건 범위가 샘터의 위치를 기준으로 -10000000 ~ 10000000 이렇게 입력되는 샘터의 위치마다 다르기 때문에 !! 배열 길이를 제한하기 어려웠다
set 도 set인데 unordered_set이 더 속도가 빠르다 해서 걍 이걸 사용해봄
1. 여태 풀었던 숨박꼭질 시리즈와 유사함 약간 숨바꼭질 염불하는 사람같은데 이렇게 일차원으로 입력되는건 어쩔 수 없다 그것만 생각남
2. 방문 체크 배열이 없기 때문에 set로 방문 즉, 이미 샘터가 있거나 집 지은곳을 체크할거임
3. 샘터위치의 범위를 보면 int는 터질거 같아서 long long type으로 체크
4. 그 이후는 보통 BFS와 탐색방법 똑같다. 대신 집을 지을 수 있는건 샘터 위치를 기준으로 앞뒤로 움직이면서 가능하며 처음 입력된 샘터의 위치를 기준으로 거리를 누적계산하며 더해준다.
- 처음에 계속 83%에서 틀렸습니다가 나왔는데 내 생각에는 기존 BFS 방식처럼 각 입력되는 샘터 위치의 기준으로 나온 범위를
공통 범위라 생각하여 집이 지어질 수 있는 좌표를 고정으로 제한해서 그런거 같다. 그 부분을 주석 처리하고 재 재출하니까 성공했다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_set>
using namespace std;
int n,k;
int dx[2] = {-1,1};
int main(void){
cin>>n>>k;
queue<pair<long long,long long> > que;
unordered_set<long long> st;
int a;
for(int i=0; i<n; i++){
cin>>a;
que.push(make_pair(a,a));
st.insert(a);
}
long long result = 0;
while(!que.empty()){
long long x = que.front().first;
long long dis = que.front().second;
que.pop();
for(int i=0; i<2; i++){
long long nx = x +dx[i];
//if(nx<-100000000 || nx>100000000 ) continue; <- 이 부분 때문에83%에서 틀림
if(st.count(nx)>=1) continue;
k-=1;
result += abs(nx-dis);
if(k==0){
cout<<result<<"\n";
return 0;
}
que.push(make_pair(nx,dis));
st.insert(nx);
}
}
}
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
<틀린 풀이>
-첫 번째 접근 : 조합 (전체의 벽중에 K를 선택하여 0으로 바꿔줌) + BFS탐색 -> 시간 초과
아마 모든 조건을 다 찾아보기 때문에 시간초과가 나는거같다.
코드 아까워서 시간초과난 코드도 기록함 ㄱ-
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n,m,k;
string map[1005];
int ch[1005][1005];
int dx[4] = {-1,0,1,0};
int dy[4] ={0,1,0,-1};
int result = 2147000000;
int BFS(){
queue<pair<int,int> > que;
memset(ch,0,sizeof(ch));
que.push(make_pair(0,0));
ch[0][0] = 1;
while(!que.empty()){
int x = que.front().first;
int y = que.front().second;
que.pop();
if(x== n-1 && y == m-1) {
return ch[x][y];
}
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
if(map[nx][ny]!='0' || ch[nx][ny]!=0) continue;
que.push(make_pair(nx,ny));
ch[nx][ny] = ch[x][y]+1;
}
}
return -1;
}
void DFS(int L){
if(L==k){
if(BFS() == -1) {
return;
}
else {
result = min(result,BFS());
return;
}
}
else{
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(map[i][j] == '1'){
map[i][j] = '0';
DFS(L+1);
map[i][j] = '1';
}
}
}
}
}
int main(void){
cin>>n>>m>>k;
for(int i=0; i<n; i++){
cin>>map[i];
}
DFS(0);
if(result ==2147000000 ){
cout<<-1<<"\n";
}
else{
cout<<result<<"\n";
}
}
<재 시도한 풀이>
- 예전에 풀었던 벽 부수고 이동하기 처럼 3차원 배열을 사용해서 재 접근했다.
( 왜 처음에 바로 생각을 못했을까 훨씬 간단한 방법이었는데,,, 머릿속에 조합밖에 없었나봄 ㄱ- ㅋㅋㅋㅋ)
- 벽을 부순 개수 = 즉, 벽인데도 지나간 개수를 따로 배열에 저장하며 탐색했다.
탐색 가능한 방법은 2가지 이다.
공통 조건 : 이동할 위치에 방문하지 않았어야함
1. 다음 이동할 위치에 벽이 있으며, 벽이 있는데 지나간 개수가 k보다 작다면 탐색할 수 있도록 큐에 넣어준다.
2. 다음 이동할 위치에 벽이 없다면 탐색가능하기 때문에 큐에 넣어준다.
따로 거리는 탐색 체크 배열을 이용하여 갱신해주며 탐색했다.
주어진 조건에서 시작점도 탐색 거리를 1로 쳐준다 해서 0,0 위치에 1을 넣고 시작함 !!!
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n,m,k;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
string map[1005];
int ch[1005][1005][11];
struct State{
int x,y,wall;
State(int a, int b, int c){
x = a;
y = b;
wall = c;
}
};
int BFS(){
memset(ch,0,sizeof(ch));
queue<State> que;
que.push(State(0,0,0));
ch[0][0][0] = 1;
while(!que.empty()){
int x = que.front().x;
int y = que.front().y;
int wall = que.front().wall;
que.pop();
if(x == n-1 && y== m-1){
return ch[x][y][wall];
}
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
if(ch[nx][ny][wall]!=0) continue;
if(map[nx][ny]=='1' && wall != k){
que.push(State(nx,ny,wall+1));
ch[nx][ny][wall+1] = ch[x][y][wall]+1;
}
else if(map[nx][ny]=='0'){
que.push(State(nx,ny,wall));
ch[nx][ny][wall] = ch[x][y][wall]+1;
}
}
}
return -1;
}
int main(void){
cin>>n>>m>>k;
for(int i=0; i<n; i++){
cin>>map[i];
}
cout<<BFS()<<"\n";
}
'Algorithm > BOJ' 카테고리의 다른 글
| [ 백준 ] 17일차 (0) | 2021.09.05 |
|---|---|
| [ 백준 ] 16일차 (0) | 2021.09.03 |
| [ 백준 ] 14일차 (0) | 2021.09.01 |
| [ 백준 ] 13일차 (0) | 2021.08.31 |
| [ 백준 ] 12일차 (0) | 2021.08.30 |