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
- 다익스트라
- 엘라스틱서치
- 시뮬레이션
- 네트워크플로우
- 세그먼트트리
- 자바PS
- COSPRO
- 알고리즘
- 01BFS
- 백준코딩테스트
- PS
- GatherTown
- dp
- 구현
- java
- spring
- 다이나믹프로그래밍
- 이젠 골드구현도 어렵네..
- 우선순위큐
- COSPROJAVA1급
- 백준
- 재귀함수
- 게더타운시작
- deque
- QUICKSTARTGUIDE
- 완전탐색
- BFS
- DFS
- 취득후기
- YBMCOS
Archives
- Today
- Total
공부공간
BOJ - 17836 ) 공주님을 구해라! 본문
https://www.acmicpc.net/problem/17836
17836번: 공주님을 구해라!
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다. 마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출
www.acmicpc.net
(1,1)에서 (N,M)이동할때 마검 그람을 얻으면 모든벽을 부수면서 진행할 수있는 문제이다.
벽부수고 이동하기처럼, 방문처리를 따로 해줄 수 있지만, 모든벽을 부수고 (N,M)으로 간다는것은
현재 시점에서 (N,M)까지 유클리디안 거리를 의미한다.
따라서 그냥 BFS한 값과 비교하여 작은값을 선택해준다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class 공주님을구해라 {
public static class node{
int y,x,time;
boolean isGet;
public node(int y, int x, int time, boolean isGet) {
this.y = y;
this.time = time;
this.x = x;
this.isGet = isGet;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int tt = Integer.parseInt(st.nextToken());
boolean visit[][] = new boolean[y][x];
int map[][] = new int[y][x];
for(int i = 0 ; i < y; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j < x ; j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int answer = -1;
int answer_= -1;
int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
ArrayDeque<node> dq = new ArrayDeque<>();
dq.add(new node(0,0,0,false));
visit[0][0] = true;
int t = tt;
while(!dq.isEmpty() && t>=0) {
t--;
int size = dq.size();
while(size >0) {
node now = dq.poll();
if(now.isGet) {
answer = now.time + (y -1 - now.y ) + (x-1 - now.x );
}
if(now.x == x-1 && now.y == y-1) {
answer_ = now.time;
}
for(int i = 0 ; i < 4 ; i ++) {
int ny = now.y+dir[i][0];
int nx = now.x+dir[i][1];
if(ny >=0 && nx >=0 && nx < x && ny < y) {
if(!visit[ny][nx] && map[ny][nx] !=1) {
if(map[ny][nx] ==2) {
visit[ny][nx] = true;
dq.addFirst(new node(ny,nx,now.time+1,true));
} else if(map[ny][nx]==0) {
visit[ny][nx] = true;
dq.add(new node(ny,nx,now.time+1, false));
}
}
}
}
size--;
}
}
if(answer_ == -1 && answer >0 && tt >=answer ) {
System.out.println(answer);
} else if( answer_ > 0 && answer == -1) {
System.out.println(answer_);
} else if( answer_ > 0 && answer > 0) {
answer = answer_ > answer ? answer : answer_;
System.out.println(answer);
} else {
System.out.println("Fail");
}
}
}
'알고리즘 > 완전탐색(BFS,DFS)' 카테고리의 다른 글
BOJ - 10971 ) 외판원 순회2 (0) | 2020.05.07 |
---|---|
BOJ - 17244 ) 아맞다우산 (0) | 2020.05.06 |
BOJ - 3109 ) 빵집 (0) | 2020.04.19 |
BOJ - 1600 ) 말이 되고픈 원숭이 (0) | 2020.04.19 |
BOJ - 14868 ) 문명 (0) | 2020.04.18 |
Comments