-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path230330.html
More file actions
101 lines (99 loc) · 18.2 KB
/
230330.html
File metadata and controls
101 lines (99 loc) · 18.2 KB
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>13913번 - 숨바꼭질 4</title>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.7.0/styles/default.min.css">
<link href="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0-alpha1/dist/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-GLhlTQ8iRABdZLl6O3oVMWSktQOp6b7In1Zl3/Jr59b6EGGoI1aFkw7cmDA6j6gD" crossorigin="anonymous">
<script src="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0-alpha1/dist/js/bootstrap.bundle.min.js" integrity="sha384-w76AqPfDkMBDXo30jS1Sgez6pr3x5MlQ1ZAGC+nuZB+EYdgRZgiwxhTBTkF7CXvN" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.7.0/highlight.min.js"></script>
<link href="./static/css/main.css" rel="stylesheet">
</head>
<body>
<div class="md-container">
<h2 class="fw-bold">13913번 - 숨바꼭질 4</h2>
<h4 id="-">분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색</h4>
<h4 id="-">문제</h4>
<p>수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.</p>
<p>수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.</p>
<h4 id="-">풀이</h4>
<p>개인적으로 아쉬움이 많이 남는 문제였다.</p>
<p>처음에는 지나온 경로를 큐의 Node에 저장을 했었다.</p>
<p>새로운 Node를 만들어 add할 때마다 새로운 List를 만들어야한다. List는 참조변수 이기때문에 계속해서 새로운 리스트를 만들어줘야 한다.</p>
<p>그렇지 않으면 경로가 계속해서 중첩되서 add 될 것이다.</p>
<p>새로 리스트를 계속 만든다고 한다면 bfs를 반복하면서 생기는 노드 개수에다가 지나온 경로 곱한 것만큼 시간이 걸린 것이다.(내가 시간초과가 된 주된 원인)</p>
<p>이를 해결하지 못해서 결국 다른 곳에서 힌트를 얻었다.</p>
<p>일반적인 다익스트라랑 달리 이동하는 데에 드는 비용은 무조건 1씩 추가된다.</p>
<p>이 말은 즉, 한 번 방문한 노드를 다른 경로로 다시 방문했을 때 비용이 더 쌀 수 있는 방법이 존재하지 않는다.</p>
<p>따라서 임의의 한 노드가 가지는 이전 노드는 무조건 한개이다. 그러므로 int[] 배열은 이용해서 이전 노드를 LinkedList 같이 저장하고 이를 거꾸로 출력하면 된다..</p>
<div class="sourceCode" id="cb1"><pre
class="sourceCode java"><code class="sourceCode java"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">io</span><span class="op">.</span><span class="im">BufferedReader</span><span class="op">;</span></span>
<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">io</span><span class="op">.</span><span class="im">IOException</span><span class="op">;</span></span>
<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">io</span><span class="op">.</span><span class="im">InputStreamReader</span><span class="op">;</span></span>
<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a><span class="kw">import</span> <span class="im">java</span><span class="op">.</span><span class="im">util</span><span class="op">.*;</span></span>
<span id="cb1-5"><a href="#cb1-5" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-6"><a href="#cb1-6" aria-hidden="true" tabindex="-1"></a><span class="kw">class</span> <span class="bu">Node</span> <span class="op">{</span></span>
<span id="cb1-7"><a href="#cb1-7" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> position<span class="op">,</span>cost<span class="op">;</span></span>
<span id="cb1-8"><a href="#cb1-8" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-9"><a href="#cb1-9" aria-hidden="true" tabindex="-1"></a> <span class="kw">public</span> <span class="bu">Node</span><span class="op">(</span><span class="dt">int</span> position<span class="op">,</span> <span class="dt">int</span> cost<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-10"><a href="#cb1-10" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">position</span> <span class="op">=</span> position<span class="op">;</span></span>
<span id="cb1-11"><a href="#cb1-11" aria-hidden="true" tabindex="-1"></a> <span class="kw">this</span><span class="op">.</span><span class="fu">cost</span> <span class="op">=</span> cost<span class="op">;</span></span>
<span id="cb1-12"><a href="#cb1-12" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-13"><a href="#cb1-13" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-14"><a href="#cb1-14" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span>
<span id="cb1-15"><a href="#cb1-15" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-16"><a href="#cb1-16" aria-hidden="true" tabindex="-1"></a><span class="kw">public</span> <span class="kw">class</span> Main <span class="op">{</span></span>
<span id="cb1-17"><a href="#cb1-17" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span> n<span class="op">,</span> k<span class="op">;</span></span>
<span id="cb1-18"><a href="#cb1-18" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="bu">Queue</span><span class="op"><</span><span class="bu">Node</span><span class="op">></span> queue<span class="op">;</span></span>
<span id="cb1-19"><a href="#cb1-19" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span><span class="op">[]</span> dp<span class="op">;</span></span>
<span id="cb1-20"><a href="#cb1-20" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span><span class="op">[]</span> savePath<span class="op">;</span></span>
<span id="cb1-21"><a href="#cb1-21" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-22"><a href="#cb1-22" aria-hidden="true" tabindex="-1"></a> <span class="kw">public</span> <span class="dt">static</span> <span class="dt">void</span> <span class="fu">main</span><span class="op">(</span><span class="bu">String</span><span class="op">[]</span> args<span class="op">)</span> <span class="kw">throws</span> <span class="bu">IOException</span> <span class="op">{</span></span>
<span id="cb1-23"><a href="#cb1-23" aria-hidden="true" tabindex="-1"></a> <span class="bu">BufferedReader</span> br <span class="op">=</span> <span class="kw">new</span> <span class="bu">BufferedReader</span><span class="op">(</span><span class="kw">new</span> <span class="bu">InputStreamReader</span><span class="op">(</span><span class="bu">System</span><span class="op">.</span><span class="fu">in</span><span class="op">));</span></span>
<span id="cb1-24"><a href="#cb1-24" aria-hidden="true" tabindex="-1"></a> <span class="bu">String</span><span class="op">[]</span> inputArr <span class="op">=</span> br<span class="op">.</span><span class="fu">readLine</span><span class="op">().</span><span class="fu">split</span><span class="op">(</span><span class="st">" "</span><span class="op">);</span></span>
<span id="cb1-25"><a href="#cb1-25" aria-hidden="true" tabindex="-1"></a> n <span class="op">=</span> <span class="bu">Integer</span><span class="op">.</span><span class="fu">parseInt</span><span class="op">(</span>inputArr<span class="op">[</span><span class="dv">0</span><span class="op">]);</span></span>
<span id="cb1-26"><a href="#cb1-26" aria-hidden="true" tabindex="-1"></a> k <span class="op">=</span> <span class="bu">Integer</span><span class="op">.</span><span class="fu">parseInt</span><span class="op">(</span>inputArr<span class="op">[</span><span class="dv">1</span><span class="op">]);</span></span>
<span id="cb1-27"><a href="#cb1-27" aria-hidden="true" tabindex="-1"></a> dp <span class="op">=</span> <span class="kw">new</span> <span class="dt">int</span><span class="op">[</span><span class="dv">100001</span><span class="op">];</span></span>
<span id="cb1-28"><a href="#cb1-28" aria-hidden="true" tabindex="-1"></a> savePath <span class="op">=</span> <span class="kw">new</span> <span class="dt">int</span><span class="op">[</span><span class="dv">100001</span><span class="op">];</span></span>
<span id="cb1-29"><a href="#cb1-29" aria-hidden="true" tabindex="-1"></a> <span class="bu">Arrays</span><span class="op">.</span><span class="fu">fill</span><span class="op">(</span>dp<span class="op">,</span> <span class="op">(</span><span class="dt">int</span><span class="op">)</span> <span class="fl">1e9</span><span class="op">);</span></span>
<span id="cb1-30"><a href="#cb1-30" aria-hidden="true" tabindex="-1"></a> queue <span class="op">=</span> <span class="kw">new</span> <span class="bu">LinkedList</span><span class="op"><>();</span></span>
<span id="cb1-31"><a href="#cb1-31" aria-hidden="true" tabindex="-1"></a> queue<span class="op">.</span><span class="fu">add</span><span class="op">(</span><span class="kw">new</span> <span class="bu">Node</span><span class="op">(</span>n<span class="op">,</span> <span class="dv">0</span><span class="op">));</span></span>
<span id="cb1-32"><a href="#cb1-32" aria-hidden="true" tabindex="-1"></a> <span class="bu">System</span><span class="op">.</span><span class="fu">out</span><span class="op">.</span><span class="fu">println</span><span class="op">(</span><span class="fu">getFastestWay</span><span class="op">());</span></span>
<span id="cb1-33"><a href="#cb1-33" aria-hidden="true" tabindex="-1"></a> <span class="dt">int</span> current <span class="op">=</span> k<span class="op">;</span></span>
<span id="cb1-34"><a href="#cb1-34" aria-hidden="true" tabindex="-1"></a> <span class="bu">List</span><span class="op"><</span><span class="bu">Integer</span><span class="op">></span> res <span class="op">=</span> <span class="kw">new</span> <span class="bu">ArrayList</span><span class="op"><>();</span></span>
<span id="cb1-35"><a href="#cb1-35" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span> <span class="op">(</span>current <span class="op">!=</span> n<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-36"><a href="#cb1-36" aria-hidden="true" tabindex="-1"></a> res<span class="op">.</span><span class="fu">add</span><span class="op">(</span>current<span class="op">);</span></span>
<span id="cb1-37"><a href="#cb1-37" aria-hidden="true" tabindex="-1"></a> current <span class="op">=</span> savePath<span class="op">[</span>current<span class="op">];</span></span>
<span id="cb1-38"><a href="#cb1-38" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-39"><a href="#cb1-39" aria-hidden="true" tabindex="-1"></a> res<span class="op">.</span><span class="fu">add</span><span class="op">(</span>current<span class="op">);</span></span>
<span id="cb1-40"><a href="#cb1-40" aria-hidden="true" tabindex="-1"></a> <span class="cf">for</span> <span class="op">(</span><span class="dt">int</span> i <span class="op">=</span> res<span class="op">.</span><span class="fu">size</span><span class="op">()</span> <span class="op">-</span> <span class="dv">1</span><span class="op">;</span> i <span class="op">></span> <span class="op">-</span><span class="dv">1</span><span class="op">;</span> i<span class="op">--)</span></span>
<span id="cb1-41"><a href="#cb1-41" aria-hidden="true" tabindex="-1"></a> <span class="bu">System</span><span class="op">.</span><span class="fu">out</span><span class="op">.</span><span class="fu">printf</span><span class="op">(</span><span class="st">"</span><span class="sc">%d</span><span class="st"> "</span><span class="op">,</span> res<span class="op">.</span><span class="fu">get</span><span class="op">(</span>i<span class="op">));</span></span>
<span id="cb1-42"><a href="#cb1-42" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-43"><a href="#cb1-43" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-44"><a href="#cb1-44" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">int</span> <span class="fu">getFastestWay</span><span class="op">()</span> <span class="op">{</span></span>
<span id="cb1-45"><a href="#cb1-45" aria-hidden="true" tabindex="-1"></a> <span class="cf">while</span> <span class="op">(</span>queue<span class="op">.</span><span class="fu">size</span><span class="op">()</span> <span class="op">></span> <span class="dv">0</span><span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-46"><a href="#cb1-46" aria-hidden="true" tabindex="-1"></a> <span class="bu">Node</span> node <span class="op">=</span> queue<span class="op">.</span><span class="fu">poll</span><span class="op">();</span></span>
<span id="cb1-47"><a href="#cb1-47" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>node<span class="op">.</span><span class="fu">position</span> <span class="op">==</span> k<span class="op">)</span></span>
<span id="cb1-48"><a href="#cb1-48" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> node<span class="op">.</span><span class="fu">cost</span><span class="op">;</span></span>
<span id="cb1-49"><a href="#cb1-49" aria-hidden="true" tabindex="-1"></a> <span class="fu">addNode</span><span class="op">(</span>node<span class="op">.</span><span class="fu">position</span> <span class="op">-</span> <span class="dv">1</span><span class="op">,</span> node<span class="op">.</span><span class="fu">cost</span><span class="op">,</span> node<span class="op">.</span><span class="fu">position</span><span class="op">);</span></span>
<span id="cb1-50"><a href="#cb1-50" aria-hidden="true" tabindex="-1"></a> <span class="fu">addNode</span><span class="op">(</span>node<span class="op">.</span><span class="fu">position</span> <span class="op">+</span> <span class="dv">1</span><span class="op">,</span> node<span class="op">.</span><span class="fu">cost</span><span class="op">,</span> node<span class="op">.</span><span class="fu">position</span><span class="op">);</span></span>
<span id="cb1-51"><a href="#cb1-51" aria-hidden="true" tabindex="-1"></a> <span class="fu">addNode</span><span class="op">(</span>node<span class="op">.</span><span class="fu">position</span> <span class="op">*</span> <span class="dv">2</span><span class="op">,</span> node<span class="op">.</span><span class="fu">cost</span><span class="op">,</span> node<span class="op">.</span><span class="fu">position</span><span class="op">);</span></span>
<span id="cb1-52"><a href="#cb1-52" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-53"><a href="#cb1-53" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span> <span class="op">-</span><span class="dv">1</span><span class="op">;</span></span>
<span id="cb1-54"><a href="#cb1-54" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-55"><a href="#cb1-55" aria-hidden="true" tabindex="-1"></a></span>
<span id="cb1-56"><a href="#cb1-56" aria-hidden="true" tabindex="-1"></a> <span class="dt">static</span> <span class="dt">void</span> <span class="fu">addNode</span><span class="op">(</span><span class="dt">int</span> x<span class="op">,</span> <span class="dt">int</span> cost<span class="op">,</span> <span class="dt">int</span> pre<span class="op">)</span> <span class="op">{</span></span>
<span id="cb1-57"><a href="#cb1-57" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span><span class="dv">0</span> <span class="op">></span> x <span class="op">||</span> x <span class="op">></span> <span class="dv">100000</span><span class="op">)</span></span>
<span id="cb1-58"><a href="#cb1-58" aria-hidden="true" tabindex="-1"></a> <span class="cf">return</span><span class="op">;</span></span>
<span id="cb1-59"><a href="#cb1-59" aria-hidden="true" tabindex="-1"></a> <span class="cf">if</span> <span class="op">(</span>cost <span class="op">+</span> <span class="dv">1</span> <span class="op"><</span> dp<span class="op">[</span>x<span class="op">])</span> <span class="op">{</span></span>
<span id="cb1-60"><a href="#cb1-60" aria-hidden="true" tabindex="-1"></a> dp<span class="op">[</span>x<span class="op">]</span> <span class="op">=</span> cost <span class="op">+</span> <span class="dv">1</span><span class="op">;</span></span>
<span id="cb1-61"><a href="#cb1-61" aria-hidden="true" tabindex="-1"></a> queue<span class="op">.</span><span class="fu">add</span><span class="op">(</span><span class="kw">new</span> <span class="bu">Node</span><span class="op">(</span>x<span class="op">,</span> cost <span class="op">+</span> <span class="dv">1</span><span class="op">));</span></span>
<span id="cb1-62"><a href="#cb1-62" aria-hidden="true" tabindex="-1"></a> savePath<span class="op">[</span>x<span class="op">]</span> <span class="op">=</span> pre<span class="op">;</span></span>
<span id="cb1-63"><a href="#cb1-63" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-64"><a href="#cb1-64" aria-hidden="true" tabindex="-1"></a> <span class="op">}</span></span>
<span id="cb1-65"><a href="#cb1-65" aria-hidden="true" tabindex="-1"></a><span class="op">}</span></span></code></pre></div>
</div>
</body>
</html>