# 유형 : 시뮬레이션

# 난이도 : 실버 3

# 그냥 반복문을 돌리면 시간초과 또는 메모리 초과가 날 것같아서, 자릿수를 이용하는 방식으로 해결하였다. 아래 표는 각 구간의 개수이다. 따라서 일의 자리는 1 * 9, 십의 자리는 2 * 90, 백의 자리는 3 * 900 이런식으로 진행하다가, 마지막 자리수는 음 예를 들어 1542라고 생각해보면 1542 - 1000 + 1 => 543개 마지막 자리수의 단위(1000)를 빼주고 1을 더해준 다음 자릿수(4)를 곱해준다.

1~9 9
10~99 90
100~999 900
1000~9999 9000

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p1748 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String num = br.readLine();
        int len = num.length();
        
        int N = Integer.parseInt(num);
        
        int tmp = 9;
        int result = 0;
        for(int i=1; i<len; i++) {
            result += i*tmp;
            tmp*=10;
        }
        
        int last =(int)( N - Math.pow(10, len-1)+1) * len;
        result += last;
        System.out.println(result);
        
    }
}    
 
 cs

'백준' 카테고리의 다른 글

#백준_2980 도로와 신호등 - Java 자바  (0) 2020.02.26
#백준_3048 개미 - Java 자바  (0) 2020.02.25
#백준_1952 달팽이2 - Java 자바  (0) 2020.02.22
#백준_2842 집배원 한상덕 - Java 자바  (0) 2020.02.21
#백준_1331 나이트 투어 - Java 자바  (0) 2020.02.21

# 유형 : 구현, 탐색

# 난이도 : 브론즈 1

# 이미 방문한 곳을 가거나, 범위에서 벗어나면 그 때가 방향을 꺾는 시점이라는 것을 안다면 쉽게 풀 수 있다.

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1952 {
    static boolean visit[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine());
         int M,N;
         M = Integer.parseInt(st.nextToken());
         N = Integer.parseInt(st.nextToken());
         
         visit = new boolean[M][N];
         
         int x = 0;
         int y = 0;
         int dir = 1;
         int cnt = 0;
         
         while(true) {
             if(visit[y][x])
                 break;
             visit[y][x] = true;
             
             int newX = x + moveX[dir];
             int newY = y + moveY[dir];
             
             if(0>newX || newX>=N || 0>newY || newY >= M || visit[newY][newX]) {
                 if(dir==3)
                     dir = 0;
                 else
                     dir++;
                 cnt++;
             }
             x = x + moveX[dir];
             y = y + moveY[dir];
        }
         
        System.out.println(cnt-1);
         
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_3048 개미 - Java 자바  (0) 2020.02.25
#백준_1748 수 이어 쓰기 1 - Java 자바  (0) 2020.02.22
#백준_2842 집배원 한상덕 - Java 자바  (0) 2020.02.21
#백준_1331 나이트 투어 - Java 자바  (0) 2020.02.21
#백준_5427 불 - Java 자바  (0) 2020.02.20

# 유형 : 탐색, BFS, 투포인터

# 난이도 : 플래티넘 V

# 플래티넘 난이도 치고 그렇게 어렵지 않았다. 피로도 구간을 BFS + 투포인터를 이용하여 차이가 최소일 때를 찾으면 되는 문제였다. 

우선 피로도를 중복 없이 입력받으면서, 정렬을 한다. 그리고 나서 low, high 포인트를 지정하여 늘려가며 최소인 구간을 찾으면 되는 문제이다. 첫 번째 테스트케이스는 아래와 같이 진행된다. low~high 구간에 있는 땅만 밟으면서 이동시키면 된다.

3(index = 0) 4(index = 1) 5(index = 2) 7(index = 3) 8(index = 4) 9(index = 5)
low,high(초기)          
low high        
low   high      
low     high    
low       high(집 all 방문)  
  low     high  
    low     high

 

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
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2842 {
    static int N, House, Min=999999;
    static Point start;
    static boolean visit[][];
    static char map[][];
    static int arr[][];
    static ArrayList<Integer> arrList = new ArrayList<>();
    static int moveX[] = {0,1,1,1,0,-1,-1,-1};
    static int moveY[] = {-1,-1,0,1,1,1,0,-1};
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        arr = new int[N][N];
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<N; j++) {
                char ch = str.charAt(j);
                
                if(ch == 'P')
                    start = new Point(j,i);
                if(ch == 'K')
                    House++;
                
                map[i][j] = ch;
            }
        }
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                int val = Integer.parseInt(st.nextToken());
                arr[i][j] = val;
                if(!arrList.contains(val))
                    arrList.add(val);
            }
        }
        Collections.sort(arrList);
        
        bfs();
        
    }
    public static void bfs() {
        int low=0, high=0;
        while(low<arrList.size()) {
            visit = new boolean[N][N];
            Queue<Point> queue = new LinkedList<Point>();
            int val = arr[start.y][start.x];
            if(arrList.get(low)<= val && val<=arrList.get(high)) {
                visit[start.y][start.x] = true;
                queue.add(new Point(start.x, start.y));
                
            }
            int count = 0;
            while(!queue.isEmpty()) {
                Point po = queue.poll();
                if(map[po.y][po.x] == 'K') {
                    count++;
                }
                
                for(int d=0; d<8; d++) {
                    int newY = po.y + moveY[d];
                    int newX = po.x + moveX[d];
                    
                    if(0<=newY && newY<N && 0<=newX && newX<N && !visit[newY][newX]) {
                        int nextVal = arr[newY][newX];
                        if(arrList.get(low)<= nextVal && nextVal<=arrList.get(high)) {
                            visit[newY][newX] = true;
                            queue.add(new Point(newX,newY));
                        }
                    
                    }
                }
            }
            if(House == count) {
                Min = Math.min(Min, arrList.get(high) - arrList.get(low));
                low++;
            }else if(high + 1 < arrList.size()) {
                high++;
            }else
                break;
        }
        
        System.out.println(Min);
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1748 수 이어 쓰기 1 - Java 자바  (0) 2020.02.22
#백준_1952 달팽이2 - Java 자바  (0) 2020.02.22
#백준_1331 나이트 투어 - Java 자바  (0) 2020.02.21
#백준_5427 불 - Java 자바  (0) 2020.02.20
#백준_1173 운동 - Java 자바  (0) 2020.02.20

# 유형 : 시뮬레이션

# 같은 곳 두번 가는 예외처리를 생각해주면 바로 풀 수 있던 문제.

# 난이도 : 실버 V

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p1331 {
    static int moveX[] = {1,2,2,1,-1,-2,-2,-1};
    static int moveY[] = {2,1,-1,-2,-2,-1,1,2};
    static String str[];
    static boolean visit[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = new String[37];
        for(int i=0; i<36; i++) {
            str[i] = br.readLine();
        }
        str[36] = str[0];
        int index=0;
        visit = new boolean[6][6];
        boolean check = true;
        while(index<36) {
            String current = str[index];
            String next = str[index+1];
            
            char current_x = current.charAt(0);
            char current_y = current.charAt(1);
            
            visit[current_y -'0'-1][current_x - 'A'] = true;
            
            char next_x = next.charAt(0);
            char next_y = next.charAt(1);
            
            int diff_x = Math.abs(current_x - next_x);
            int diff_y = Math.abs(current_y - next_y);
            boolean isTrue = false;
            for(int d=0; d<8; d++) {
                if(moveX[d] == diff_x && moveY[d] == diff_y) {
                    isTrue = true;
                    break;
                }
            }
            if(!isTrue) {
                check = false;
                System.out.println("Invalid");
                return;
            }
            if(visit[next_y-'0'-1][next_x-'A']) {
                if(index!=35) {
                    check = false;
                    System.out.println("Invalid");
                    return;
                }
            }
            
            index++;
        }
        if(check)
            System.out.println("Valid");
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1952 달팽이2 - Java 자바  (0) 2020.02.22
#백준_2842 집배원 한상덕 - Java 자바  (0) 2020.02.21
#백준_5427 불 - Java 자바  (0) 2020.02.20
#백준_1173 운동 - Java 자바  (0) 2020.02.20
#백준_2174 로봇 시뮬레이션 - Java 자바  (0) 2020.02.19

# 유형 : 탐색, BFS

# 난이도 : 골드 IV

# 괜히 리스트도 쓰고 조건문 너무 구체적으로 하다가 메모리초과가 났다. 코드를 줄일 수 있는 만큼 줄이고, 불필요한 코드를 최대한 없애고 조건을 수정하니 정답이었다. 방법은 1) 불을 먼저 bfs를 통해 탐색해준다. 동시에 진행이라고 하지만 불이 번지는 곳에는 결국 상근이가 못움직이는 곳이기 때문에 불을 먼저 탐색해주고 그 다음 상근이의 움직임을 BFS를 통해 탐색한다.

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
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p5427 {
    static int R,C;
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static char arr[][];
    static boolean visit[][];
    static int map[][];
    static Queue<Point> fire;
    static Point start;
    static boolean isPossible;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        for(int tc=0; tc<testCases; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            C = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            isPossible = false;
            arr = new char[R][C];
            map = new int[R][C];
            fire = new LinkedList<>();
            
            for(int r=0; r<R; r++) {
                String str = br.readLine();
                for(int c=0; c<C; c++) {
                    char ch = str.charAt(c);
                    if(ch == '@')
                        start = new Point(c,r);
                    else if(ch == '*')
                        fire.add(new Point(c,r));
                    
                    arr[r][c] = ch;
                }
            }
            bfs();
            if(!isPossible) {
                System.out.println("IMPOSSIBLE");
            }
        }
    }
    
    public static void bfs() {
        Queue<Point> queue = new LinkedList<>();
        queue.add(start);
        
        while(!queue.isEmpty()) {
            int len = fire.size();
            for(int l=0; l<len; l++) {
                Point po = fire.poll();
                for(int d=0; d<4; d++) {
                    int newX = po.x + moveX[d];
                    int newY = po.y + moveY[d];
                    if(0<=newY && newY<R && 0<=newX && newX<C && arr[newY][newX]!='#' && arr[newY][newX]!='*') {
                        arr[newY][newX] = '*';
                        fire.add(new Point(newX,newY));
                    }
                }
            }
            
            len = queue.size();
            for(int l=0; l<len; l++) {
                Point po = queue.poll();
                if((po.x == 0) || (po.x == C-1) || (po.y == 0) || (po.y == R-1)) {
                    isPossible = true;
                    System.out.println(map[po.y][po.x] + 1);
                    return;
                }
                for(int d=0; d<4; d++) {
                    int newX = po.x + moveX[d];
                    int newY = po.y + moveY[d];
                    if(0<=newY && newY<R && 0<=newX && newX<C && arr[newY][newX]=='.'){
                        map[newY][newX] = map[po.y][po.x] + 1;
                        arr[newY][newX] = '@';
                        queue.add(new Point(newX,newY));
                    }
                }
            }
            
        }
        
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2842 집배원 한상덕 - Java 자바  (0) 2020.02.21
#백준_1331 나이트 투어 - Java 자바  (0) 2020.02.21
#백준_1173 운동 - Java 자바  (0) 2020.02.20
#백준_2174 로봇 시뮬레이션 - Java 자바  (0) 2020.02.19
#백준_2931 가스관 - Java 자바  (0) 2020.02.18

#유형 : 구현, 시뮬레이션

# 난이도 : 브론즈2 

# 어떤 경우가 운동을 끝낼 수 없는 경우인지를 생각해보고 풀면 쉽게 풀 수 있다. 현재 맥박에 T 를 더했을 때 M을 초과하면서 현재 맥박이 m이면 운동을 끝낼 수 없는 경우이다.

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1173 {
    static int N,m,M,T,R;
    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());
        M = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        
        int count = 0;
        int time = 0;
        int current = m;
//        System.out.println(current);
        while(count<N) {
            if(current+T <= M) {
                count++;
                time++;
                current += T;
            }else {
                if((current - R)< m) {
                    time++;
                    current = m ;
                }else {
                    time++;
                    current -= R;
                }
            }
            
            if(current + T > M && current == m) {
                System.out.println("-1");
                return;
            }
                
//            System.out.println(current);
        }
        System.out.println(time);
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1331 나이트 투어 - Java 자바  (0) 2020.02.21
#백준_5427 불 - Java 자바  (0) 2020.02.20
#백준_2174 로봇 시뮬레이션 - Java 자바  (0) 2020.02.19
#백준_2931 가스관 - Java 자바  (0) 2020.02.18
#백준_9205 맥주 마시면서 걸어가기 - Java 자바  (0) 2020.02.17

# 유형 : 시뮬레이션, 구현

# 난이도는 골드 4인데 어렵지 않은 문제였다. 좌표를 거꾸로 줬기 때문에 그거만 생각하여 북쪽으로 이동할때는 y좌표가 감소하는것이 아닌 증가, 남쪽으로 이동할 때는 y좌표가 감소하는 것만 생각하여 이동 좌표를 수정해주면 된다. 백준 홈페이지에는 없는 추가적인 테스트 케이스를 첨부하니 여러 케이스에 대하여 실행해보면 좋을 것 같다.

 

5 4

2 2

1 1 E

5 4 W

1 F 7

2 F 7 =====> Robot 1 crashes into the wall

 

5 4
2 4
1 1 E
5 4 W
1 F 3
2 F 1
1 L 1
1 F 3 ======> Robot 1 crashes into robot 2 

 

5 4
2 2
1 1 E
5 4 W
1 L 96
1 F 2 =======> OK 


5 4
2 3
1 1 E
5 4 W
1 F 4
1 L 1
1 F 20 =======> Robot 1 crashes into robot 2

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
122
123
124
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p2174 {
    static int A,B,N,M;
    static Robot[] robot;
    static boolean isTrue=false;
    static int check[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {1,0,-1,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        N= Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        check = new int[B+1][A+1];
        robot = new Robot[N+1];
        for(int n=1; n<=N; n++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            char dir = st.nextToken().charAt(0);
            int d=0;
            if(dir=='N')
                d = 0;
            else if(dir =='E')
                d = 1;
            else if(dir =='S')
                d = 2;
            else if(dir == 'W')
                d = 3;
            check[y][x] = n;
            robot[n] = new Robot(x,y,d);
        }
        for(int m=1; m<=M; m++) {
            
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            char ch = st.nextToken().charAt(0);
            int iter = Integer.parseInt(st.nextToken());
            
            solve(num, ch, iter);
            if(isTrue)
                break;
            
        }
        if(!isTrue)
            System.out.println("OK");
        
    }
    
    
    
    private static void solve(int num, char ch, int iter) {
        // TODO Auto-generated method stub
        for(int it=0; it<iter; it++) {
            Robot rb = robot[num];
            if(ch == 'R' || ch =='L') {
                int nextDir = getDir(rb.dir, ch);
                robot[num] = new Robot(rb.x, rb.y, nextDir);
            }else if(ch == 'F') {
                int newX = rb.x + moveX[rb.dir];
                int newY = rb.y + moveY[rb.dir];
                if(1<=newX && newX<=A && 1<=newY && newY<=B) {
                    if(check[newY][newX] != 0) {
                        System.out.println("Robot "+num +" crashes into robot " + check[newY][newX]);
                        isTrue = true;
                        return;
                    }else {
                        check[rb.y][rb.x] = 0;
                        check[newY][newX] = num;
                        robot[num] = new Robot(newX, newY, rb.dir);
                    }
                }else {
                    System.out.println("Robot "+num+" crashes into the wall");
                    isTrue = true;
                    return;
                }
            }
        }
    }
    
    public static int getDir(int dir, char ch) {
        
        if(ch == 'L') {
            if(dir == 0){
                dir = 3;
            }else {
                dir--;
            }
            
        }else if(ch == 'R') {
            if(dir==3) {
                dir = 0;
            }else {
                dir++;
            }
        }
        return dir;
    }
 
 
 
    public static class Robot{
        int x;
        int y;
        int dir;
        public Robot(int x, int y, int dir) {
            this.x=x;
            this.y=y;
            this.dir=dir;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_5427 불 - Java 자바  (0) 2020.02.20
#백준_1173 운동 - Java 자바  (0) 2020.02.20
#백준_2931 가스관 - Java 자바  (0) 2020.02.18
#백준_9205 맥주 마시면서 걸어가기 - Java 자바  (0) 2020.02.17
#백준_1592 영식이와 친구들 - Java 자바  (0) 2020.02.16

# 유형 : 탐색, BFS + 시뮬레이션

# 개인적으로 많이 복잡했던 문제.. 출발지는 주어지지만 시작방향은 안주어지기 때문에 시작방향을 찾아야한다.

이 때 해커가 만약 시작점 바로 주변의 파이프를 훔쳐갔다면 4방향으로 7개의 파이프를 넣으면서 또 탐색을 해야한다.

따라서 맨 처음에 모스코바에서 시작할 때 방향을 먼저 구해야한다. BFS 방법을 사용하며 큐에서 poll한 좌표가 모스코바 인 경우 방향을 구하고, 모스코바가 아닌 경우에는 ,진행 방향에 있는 다음 좌표만 탐색을 계속 하면 된다. 탐색을 계속 진행하다가, 가스가 흐르는 방향인데 만약 그곳이 비어있다면 그 좌표가 해커가 지운 블록이다. 따라서 그 좌표를 return 하고 그 좌표에 7개의 파이프를 넣어가며 bfs를 한번 더 돌려 모든 파이프에 가스가 흐르는지 체크해주면 된다.

개인적으로 코드가 많이 지저분하다. 아이디어만 참고하는게 좋을 것같다.

 

 

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2931 {
    static ArrayList<Point> arrList = new ArrayList<>();
    static char chArr[] = {'|','-', '+', '1', '2', '3', '4'};
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int R,C;
    static char arr[][];
    static boolean visit[][];
    static Point M,Z,tmp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];
        visit = new boolean[R][C];
        for(int r=0; r<R; r++) {
            String str = br.readLine();
            for(int c=0; c<C; c++) {
                char ch = str.charAt(c);
                if(ch == 'M')
                    M = new Point(c,r);
                else if(ch == 'Z')
                    Z = new Point(c,r);
                
                
                if(ch != '.' && ch != 'M' && ch!= 'Z')
                    arrList.add(new Point(c,r));
                
                arr[r][c] = ch;
            }
        }
        bfs();
        
        Point first = new Point(tmp);
        
        first.x = tmp.x;
        first.y = tmp.y;
        
        for(int d=0; d<7; d++) {
            arr[first.y][first.x] = chArr[d];
            visit = new boolean[R][C];
            Point second;
            bfs();
            second = new Point(tmp);
            if(second.x == -1 && second.y == -1) {
                if(checkAll()) {
                    System.out.println((first.y+1)+" "+(first.x+1)+ " "+arr[first.y][first.x]);
                    return;
                }
            }
        }
    }
    
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Three> queue = new LinkedList<Three>();
        Three current = new Three(M.x, M.y, 0);
 
        boolean isTrue = false;
        queue.add(current);
        
        while(!queue.isEmpty()) {
            
            if(isTrue)
                break;
            
            Three t = queue.poll();
            
            int x = t.x;
            int y = t.y;
            int dir = t.dir;
            
            if(arr[y][x] == 'M') {
                for(int d=0; d<4; d++) {
                    int newX = x + moveX[d];
                    int newY = y + moveY[d];
 
                    if(0<=newX && newX<C && 0<=newY && newY<R) {
                        if(arr[newY][newX] == 'Z') {
                            continue;
                        }
                        if(arr[newY][newX] != '.') {
                            dir = getDir(d, arr[newY][newX]);
                            if(dir != -1) {
                                queue.add(new Three(newX, newY, dir));
                                if(!visit[newY][newX])
                                    visit[newY][newX] = true;
                            }
                        }
                    }
                }
                
                // 위 과정에서 시작점의 방향을 못 찾은 경우 => 시작지 주변이 도둑질당한경우
                if(queue.size() == 0) {
                    
                    for(int d=0; d<4; d++) {
                        
                        if(isTrue)
                            break;
                        
                        int newX = x + moveX[d];
                        int newY = y + moveY[d];
                        
                        if(0<=newX && newX<C && 0<=newY && newY<R) {
                            
                            for(int i=0; i<7; i++) {
                                visit = new boolean[R][C];
                                arr[newY][newX] = chArr[i];
                                
                                bfs();
                                if(tmp.x == -1 && tmp.y == -1) {
                                    if(checkAll()) {
                                        isTrue = true;
                                        System.out.println((y+1)+" "+(x+1)+" "+arr[y][x]);
                                        return;
                                    }
                                }
                                arr[newY][newX] = '.';
                            }
                            
                        }
                    }
                    
                }
            }else {
                int newX = x + moveX[dir];
                int newY = y + moveY[dir];
                
                if(0<=newX && newX<C && 0<=newY && newY<R) {
                    if(arr[newY][newX] == '.') {
                        tmp = new Point(newX,newY);
                        return;
                    }
                    else if(arr[newY][newX] == 'Z') {
                        tmp = new Point(-1,-1);
                        return;
                    }
                    
                    dir = getDir(dir, arr[newY][newX]);
                    if(dir == -1) {
                        tmp = new Point(newX,newY);
                        return; 
                    }
                    if(!visit[newY][newX])
                        visit[newY][newX] = true;
                    
                    queue.add(new Three(newX,newY,dir));
                }
            }
        }
    }
 
    public static boolean checkAll() {
        for(int i=0; i<arrList.size(); i++) {
            int x = arrList.get(i).x;
            int y = arrList.get(i).y;
            
            if(visit[y][x] != true)
                return false;
        }
        return true;
    }
 
    public static int getDir(int dir, char ch) {
        int d=-1;
        if(ch == '|') {
            if(dir==0 || dir==2)
                d = dir;
        }else if(ch == '-') {
            if(dir==1 || dir==3)
                d = dir;
        }else if(ch =='+') {
            d = dir;
        }else if(ch == '1') {
            if(dir == 3) {
                d = 2;
            }else if(dir == 0) {
                d = 1;
            }
        }else if(ch == '2') {
            if(dir == 3) {
                d = 0;
            }else if(dir == 2) {
                d = 1;
            }
        }else if(ch == '3') {
            if(dir == 1) {
                d = 0;
            }else if(dir ==2) {
                d = 3;
            }
        }else if(ch == '4') {
            if(dir == 1) {
                d = 2;
            }else if(dir == 0) {
                d = 3;
            }
        }
        return d;
    }
    
    public static class Three{
        int x;
        int y;
        int dir;
        public Three(int x, int y, int dir) {
            this.x=x;
            this.y=y;
            this.dir=dir;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1173 운동 - Java 자바  (0) 2020.02.20
#백준_2174 로봇 시뮬레이션 - Java 자바  (0) 2020.02.19
#백준_9205 맥주 마시면서 걸어가기 - Java 자바  (0) 2020.02.17
#백준_1592 영식이와 친구들 - Java 자바  (0) 2020.02.16
#백준_1613 역사 - Java 자바  (0) 2020.02.16

+ Recent posts

티스토리툴바