<Algorithm> 123. 이상한 피라미드 탐험(SWExpert)

1. 이상한 피라미드 탐험(SWExpert)

문제해결능력 & BFS 문제
이 문제는 예제 테스트케이스도 잘나오는데 런타임에러가 발생하길래 ArrayIndexBoundsException 예외처리를 했더니 통과가 되었다.
e.getMessage()를 해보니 인덱스가 10000이 넘어가는 경우가 발생했다. 10000 이상에 부분에 대해 처리를 안해주어서 발생한 문제였다.
좀 더 세밀하게 고민을 할 필요가 있다는 걸 다시 깨달았다. 예외처리는 정말 중요한 것 같다.

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Solution{
    static HashSet set_left;
    static HashSet set_right;
    static boolean[] visited;
    static int[] dist;
 
    public static void main(String[] args) throws IOException {
        int res = 1;
        int cnt = 1;
        set_left = new LinkedHashSet();
        set_right = new LinkedHashSet();
        int[] heigh = new int[10001];
        
        /******************************
         * 피라미드의 높이를 활용해 인접 방의 숫자를
         * 구한다. 이때 맨 좌측,맨 우측, 1번방 
         * 그외 총 4가지 경우를 판단해줘야 한다.
         * 시작 방부터 BFS 탐색을 통해서
         * 원하는 방을 만나면 탐색을 종료하고
         * 그에 해당하는 거리를 출력한다.
         *******************************/
        
        
        for(int i = 0; i  < 150 ; i ++){
            heigh[i] = res;
            res += cnt++;
            set_left.add(res); // 맨 좌측 방들
        }
        res = 1;
        cnt = 2;
        for(int i = 0; i  < 150 ; i ++){
            res += cnt++;
            set_right.add(res); // 맨 우측방들
        }
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder("");
        int T = Integer.parseInt(br.readLine());
 
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            dist = new int[10001];
            visited = new boolean[10001];
            if(a == b ) {
                sb.append("#"+(t+1)+" "+0+"\n");
                continue;
            }
 
            bfs(Math.max(a,b),Math.min(a,b),heigh);
 
            sb.append("#"+(t+1)+" "+(dist[Math.min(a,b)])+"\n");
        }
        System.out.println(sb.toString());
    }
    public  static  void bfs(int start,int target,int[] heigh){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()){
            int item = queue.poll();
            int hei = 0;
 
            for(int i = 0; i < 149; i++){
                if(heigh[i] <= item && item < heigh[i+1]){
                    hei = i+1;
                    break;
                }
            }
            if(item == 1 && target != 1)continue;
            try {
                if (set_left.contains(item)) {
                    int[] adj = new int[]{item - hei + 1, item + 1, item + hei, item + hei + 1};
                    for (int i = 0; i < adj.length; i++) {
                        if (!visited[adj[i]]) {
                            visited[adj[i]] = true;
                            queue.offer(adj[i]);
                            dist[adj[i]] = dist[item] + 1;
                            if (adj[i] == target) {
                                return;
                            }
                        }
                    }
                } else if (set_right.contains(item)) {
                    int[] adj = new int[]{item - hei, item - 1, item + hei, item + hei + 1};
                    for (int i = 0; i < adj.length; i++) {
                        if (!visited[adj[i]]) {
                            visited[adj[i]] = true;
                            queue.offer(adj[i]);
                            dist[adj[i]] = dist[item] + 1;
                            if (adj[i] == target) {
                                return;
                            }
                        }
                    }
                } else {
                    int[] adj = new int[]{item - hei, item - hei + 1, item - 1, 
                            item + 1, item + hei, item + hei + 1};
                    for (int i = 0; i < adj.length; i++) {
                        if (!visited[adj[i]]) {
                            visited[adj[i]] = true;
                            queue.offer(adj[i]);
                            dist[adj[i]] = dist[item] + 1;
                            if (adj[i] == target) {
                                return;
                            }
                        }
                    }
 
                }
            }catch (ArrayIndexOutOfBoundsException e){
            }
        }
    }
}
 
Colored by Color Scripter
cs

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Solution{
    static HashSet set_left;
    static HashSet set_right;
    static boolean[] visited;
    static int[] dist;
 
    public static void main(String[] args) throws IOException {
        int res = 1;
        int cnt = 1;
        set_left = new LinkedHashSet();
        set_right = new LinkedHashSet();
        int[] heigh = new int[10001];
        
        /******************************
         * 피라미드의 높이를 활용해 인접 방의 숫자를
         * 구한다. 이때 맨 좌측,맨 우측, 1번방 
         * 그외 총 4가지 경우를 판단해줘야 한다.
         * 시작 방부터 BFS 탐색을 통해서
         * 원하는 방을 만나면 탐색을 종료하고
         * 그에 해당하는 거리를 출력한다.
         *******************************/
        
        
        for(int i = 0; i  < 150 ; i ++){
            heigh[i] = res;
            res += cnt++;
            set_left.add(res); // 맨 좌측 방들
        }
        res = 1;
        cnt = 2;
        for(int i = 0; i  < 150 ; i ++){
            res += cnt++;
            set_right.add(res); // 맨 우측방들
        }
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder("");
        int T = Integer.parseInt(br.readLine());
 
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            dist = new int[10001];
            visited = new boolean[10001];
            if(a == b ) {
                sb.append("#"+(t+1)+" "+0+"\n");
                continue;
            }
 
            bfs(Math.max(a,b),Math.min(a,b),heigh);
 
            sb.append("#"+(t+1)+" "+(dist[Math.min(a,b)])+"\n");
        }
        System.out.println(sb.toString());
    }
    public  static  void bfs(int start,int target,int[] heigh){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()){
            int item = queue.poll();
            int hei = 0;
 
            for(int i = 0; i < 149; i++){
                if(heigh[i] <= item && item < heigh[i+1]){
                    hei = i+1;
                    break;
                }
            }
            if(item == 1 && target != 1)continue;
            
                if (set_left.contains(item)) {
                    int[] adj = new int[]{item - hei + 1, item + 1, item + hei, item + hei + 1};
                    for (int i = 0; i < adj.length; i++) {
                        if ( adj[i] <= 10000 && adj[i] >=1 && !visited[adj[i]]) {
                            visited[adj[i]] = true;
                            queue.offer(adj[i]);
                            dist[adj[i]] = dist[item] + 1;
                            if (adj[i] == target) {
                                return;
                            }
                        }
                    }
                } else if (set_right.contains(item)) {
                    int[] adj = new int[]{item - hei, item - 1, item + hei, item + hei + 1};
                    for (int i = 0; i < adj.length; i++) {
                        if (adj[i] <= 10000 && adj[i] >=1 && !visited[adj[i]]) {
                            visited[adj[i]] = true;
                            queue.offer(adj[i]);
                            dist[adj[i]] = dist[item] + 1;
                            if (adj[i] == target) {
                                return;
                            }
                        }
                    }
                } else {
                    int[] adj = new int[]{item - hei, item - hei + 1, item - 1,
                             item + 1, item + hei, item + hei + 1};
                    for (int i = 0; i < adj.length; i++) {
                        if (adj[i] <= 10000 && adj[i] >=1 && !visited[adj[i]]) {
                            visited[adj[i]] = true;
                            queue.offer(adj[i]);
                            dist[adj[i]] = dist[item] + 1;
                            if (adj[i] == target) {
                                return;
                            }
                        }
                    }
 
                }
        }
    }
}
 
Colored by Color Scripter
cs

참고 & 출처

저작자표시 비영리

'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글

<Algorithm> 125. 성수의 프로그래밍 강좌 신청(SWExpert) (0)	2019.02.26
<Algorithm> 124. 수제버거장인(SWExpert) (0)	2019.02.25
<Algorithm> 122. Contact(SWExpert) (0)	2019.02.22
<Algorithm> 121. 나는개구리로소이다(SWExpert) (0)	2019.02.21
<Algorithm> 120. 뉴스클러스터링(KAKAO) (0)	2019.02.20

블로그의 정보

57개월 BackEnd

BFine

<Algorithm> 123. 이상한 피라미드 탐험(SWExpert)

1. 이상한 피라미드 탐험(SWExpert)

참고 & 출처

'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글

블로그의 정보

활동하기

티스토리툴바

1. 이상한 피라미드 탐험(SWExpert)

참고 & 출처

'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글

블로그의 정보

활동하기

공유하기

다른 글

티스토리툴바