<Algorithm> 100. 16197번 두동전
by BFine반응형
16197번 두동전
- BFS와 문제해결능력을 필요로 하는 문제
- 이문제를 풀면서 배운점이 두가지가 있다. 하나는 ArrayList와 LinkedList 이고 두번째는 런타임에러이다.
- LinkedList를 ArrayList로 바꿨을때는 시작하자마자 시간초과가 발생했다. 이 둘의 연산속도의 차이를 확실히 느낄 수 있었다.
- 알고리즘 문제를 풀때나 연산이 많이 필요한 경우는 LinkedList를 써야겠다.
- 거의 채점이 끝나갈때 런타임에러가 발생했다. 틀렸습니다가 아니라 런타임에러라 의아해서 어디서 발생하는지 알기 위해서 일일이 try catch로 찾아서 수정을 했다. 로직 짤때 뿐만아니라 알고리즘 문제 풀때도 예외처리를 중요하다는 것을 느꼈다.
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n;
static int m;
static char[][] arr;
static boolean wall[][];
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
wall = new boolean[n][m];
arr = new char[n][m];
Queue<Pair> coinsq = new LinkedList<>();
/******************************
*BFS를 활용해서 모든 경우의 수를 count가
*10까지만 확인하여 최솟값을 구한다.
*이때 Queue에 동전의 좌표를 넣어주고
*제거하고 옮긴 위치를 다시 넣어주는 방식으로
*진행된다.
*******************************/
for(int i = 0; i < n ; i++) {
String str = br.readLine();
for(int j = 0; j < m; j++) {
arr[i][j] = str.charAt(j);
if(arr[i][j] == '#') wall[i][j] = true;
if(arr[i][j] == 'o') coinsq.add(new Pair(i, j,0));
}
}
int[] nx = {0,0,1,-1};
int[] ny = {1,-1,0,0};
while(true) {
if(coinsq.size()<2)break;
Pair coin1 = coinsq.remove();
Pair coin2 = coinsq.remove();
int count1 = coin1.count;
int count2 = coin2.count;
if(count1 >=10 || count2 >=10) break;
for(int i = 0; i < 4; i++) {
int coin1x = nx[i] + coin1.x;
int coin1y = ny[i] + coin1.y;
int coin2x = nx[i] + coin2.x;
int coin2y = ny[i] + coin2.y;
if(coin1x < 0 || coin1x >= n || coin1y < 0 || coin1y >= m) {
if(coin2x >= 0 && coin2x < n && coin2y >= 0 && coin2y < m ) {
min = Math.min(count1, min);
}
continue;
}
if(coin2x < 0 || coin2x >= n || coin2y < 0 || coin2y >= m) {
if(coin1x >= 0 && coin1x < n && coin1y >= 0 && coin1y < m ) {
min = Math.min(count2, min);
}
continue;
}
if(!wall[coin1x][coin1y]) {
coinsq.add(new Pair(coin1x, coin1y,count1+1));
}else {
coinsq.add(new Pair(coin1.x, coin1.y,count1+1));
}
if(!wall[coin2x][coin2y]) {
coinsq.add(new Pair(coin2x, coin2y,count2+1));
}else {
coinsq.add(new Pair(coin2.x, coin2.y,count2+1));
}
}
}
if(min >= 10 || min == Integer.MIN_VALUE) {
System.out.println(-1);
}else {
System.out.println(min+1); // +1이 min값 찾기 아래에 있으므로 +1을 더해준다.
}
}
}
class Pair{
int x ;
int y ;
int count;
public Pair(int x, int y,int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
|
|
|
cs |
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
| <Algorithm> 102. 모의고사(프로그래머스) (0) | 2019.02.04 |
|---|---|
| <Algorithm> 101. 2234번 성곽 (0) | 2019.02.04 |
| <Algorithm> 99. K번째수(프로그래머스) (0) | 2019.02.02 |
| <Algorithm> 98. 더맵게(프로그래머스) (0) | 2019.02.01 |
| <Algorithm> 97. 쇠막대기(프로그래머스) (0) | 2019.01.31 |
블로그의 정보
57개월 BackEnd
BFine