반응형
12-24 07:02
- Today
- Total
Link
개발하는 고라니
[백준] 13913번 : 숨바꼭질 4 본문
반응형
[BFS]
백준의 숨바꼭질 시리즈 중 4번 째 문제. 이번에는 1초 뒤 -1, +1, *2 칸으로 이동할 수 있고, end에 도착했을 때 최소 시간과 그 때의 거쳐온 과정을 나열한다. 과정을 출력하는 것은, from[]이라는 배열을 준비하고, cur정점에서 next 정점으로 n만큼의 시간을 거쳐서 갈 때,
from[next] = cur
arr[next] = n
visit[next] =true 한다.
이렇게 저장된 from[]에서 필요한 것만 빼서 List에 저장 후 역순으로 출력하면 끝
# Code </>
public class Main {
static class Element{
int next, dist;
public Element(int n, int d){
next = n;
dist = d;
}
}
static final int N = 100001;
static boolean[] visit = new boolean[N];
static int[] arr = new int[N], from = new int[N], move = {-1, 1, 0};
static void BFS(int start, int end){
Queue<Element> Q = new LinkedList<>();
visit[start] = true;
Q.add(new Element(start, 0));
while(!Q.isEmpty()){
Element e = Q.poll();
int current = e.next;
int dist = e.dist;
if(current == end) break;
move[2] = current;
for(int a=0; a<3; a++){
int next = current + move[a];
if(next < 0 || next > N-1 || visit[next]) continue;
visit[next] = true;
arr[next] = dist + 1;
from[next] = current;
Q.add(new Element(next, dist + 1));
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
List<Integer> list = new ArrayList<>();
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
BFS(start, end);
list.add(end);
int v = end;
while(v != start){
list.add(from[v]);
v = from[v];
}
System.out.println(arr[end]);
for(int i=list.size()-1; i>=0; i--)
System.out.print(list.get(i) + " ");
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 5567번 : 결혼식 (0) | 2021.02.17 |
---|---|
[백준] 5427번 : 불 (0) | 2021.02.17 |
[백준] 1600번 : 말이 되고픈 원숭이 (0) | 2021.02.17 |
[백준] 11559번 : Puyo Puyo (0) | 2021.02.16 |
[백준] 1976번 : 여행 가자 (0) | 2021.02.16 |
Comments