1417번: 국회의원 선거

첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같

www.acmicpc.net

 

# 풀이 방법

국회의원 후보들 중 다솜이가 당선되어야 하기 때문에

현재 가장 많은 투표수를 가지고 있는 후보의 표를 다솜이에게 주면서 표수를 확인하는 방식으로 문제를 풀었습니다.

 

후보 수와 그 후보의 득표 수를 저장할 info 객체를 하나 만들어 다솜이를 제외한 후보의 정보를 우선순위 큐에 넣어주었습니다.

 

while문을 돌면서 우선순위 큐가 비었거나, 다솜이를 제외한 후보들 중 가장 많은 득표수를 가지고 있는 후보와 다솜이의 득표수를 비교해 다솜이가 더 많다면 더 이상 매수할 필요가 없으니 반복문을 종료했습니다.

반대로 다솜이보다 득표수가 많다면 그 후보의 표를 다솜이에게 주기 위해 -1 / +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
50
51
52
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
 
public class Main_BJ_1417_국회의원선거 {
    
    static class Info{
        int number, vote;
 
        public Info(int number, int vote) {
            this.number = number;
            this.vote = vote;
        }
    }
    
    static int N;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Info> pq = new PriorityQueue<>(new Comparator<Info>() {
 
            @Override
            public int compare(Info o1, Info o2) {
                return (o1.vote-o2.vote)*-1;
            }
        });
        
        N = Integer.parseInt(br.readLine());
        
        Info dasom = new Info(1, Integer.parseInt(br.readLine()));
        for(int i=2;i<=N;i++) {
            pq.add(new Info(i, Integer.parseInt(br.readLine())));
        }
        
        int count=0;
        while(true) {
            if(pq.isEmpty()||dasom.vote>pq.peek().vote) break;
            
            Info temp = pq.poll();
            dasom.vote=dasom.vote+1;
            pq.add(new Info(temp.number, temp.vote-1));
            count++;
        }
        
        System.out.println(count);
 
    }
 
}
 cs

 

'문제 > 백준' 카테고리의 다른 글

백준 1918번 후위 표기식 [JAVA]  (0) 2022.04.26
백준 21608 상어 초등학교 [JAVA]  (0) 2021.12.01
백준 17143번 낚시왕 [JAVA]  (0) 2021.12.01
백준 13549번 숨바꼭질3 [JAVA]  (0) 2021.11.23
백준 3085번 사탕 게임 [JAVA]  (0) 2021.11.18
 

1918번: 후위 표기식

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의

www.acmicpc.net

 

풀이 방법

연산자에 우선순위를 부여하여 HashMap에 저장해 연산자 비교를 쉽게 할 수 있도록 했습니다.

 

만약 숫자라면 출력하고,

연산자라면 스택에 있는 연산자와 비교하여 우선순위를 이용해 스택에 저장할지 아님 출력할지를 결정했습니다.

 

또한 ')'인 경우에는 반복문을 돌면서 '('가 나올 때까지 출력했습니다.

그리고 for문이 끝난 뒤에는 stack에 저장된 값이 있다면 stack이 빌 때까지 출력해주었습니다.

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Stack;
 
public class Main_BJ_1918_후위표기식 {
    
    static HashMap<Character, Integer> hm = new HashMap<>(); 
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringBuilder sb = new StringBuilder();
        
        Stack<Character> stack = new Stack<>();
        
        hm.put('*', 3); hm.put('/', 3);
        hm.put('+', 2); hm.put('-', 2);
        hm.put('(', 1); hm.put(')', 1);
        
        String line = br.readLine();
        for(int i=0;i<line.length();i++) {
            char c = line.charAt(i);
            if(c=='(') stack.push(c);
            else if(c>=65 && c<=90) sb.append(c);
            else if(c=='+' || c=='-' || c=='*' || c=='/') {
                while(!stack.isEmpty()) {
                    if(priority(c)<=priority(stack.peek())) {
                        sb.append(stack.pop());
                    }else break;
                }
                stack.push(c);
            }else if(c==')') {
                while(!stack.isEmpty()) {
                    char top = stack.pop();
                    if(top=='(') break;
                    else sb.append(top);
                }
            }
        }
        
        while(!stack.isEmpty()) sb.append(stack.pop());
        
        System.out.println(sb.toString());
    }

    public static int priority(char key) {
        return hm.get(key);
    }
 
}
 
 cs

 

​

'문제 > 백준' 카테고리의 다른 글

백준 1417번 국회의원 선거 [JAVA]  (0) 2022.06.06
백준 21608 상어 초등학교 [JAVA]  (0) 2021.12.01
백준 17143번 낚시왕 [JAVA]  (0) 2021.12.01
백준 13549번 숨바꼭질3 [JAVA]  (0) 2021.11.23
백준 3085번 사탕 게임 [JAVA]  (0) 2021.11.18
 

21608번: 상어 초등학교

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호

www.acmicpc.net

 

풀이 방법

학생의 자리를 정하는데 다음과 같은 규칙이 존재합니다.

  1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
  2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
  3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

해당 학생이 좋아하는 학생의 번호를 저장하기 위해서 배열 안에 List를 넣어주었습니다.

해당 조건에 맞는 학생의 자리를 찾기위해 like와 empty배열을 사용하여 좋아하는 학생이 얼마나 인접해있는지와 비어있는 칸은 몇 개인지를 확인해 배열에 저장해주었습니다. 배열에 저장된 데이터를 기준으로 조건 1,2,3을 충족하는 경우에 해당 학생 자리를 배치해주는 방식으로 구현했습니다.

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_BJ_21608_상어초등학교 {
    
    static int N, answer=0;
    static int [][] seat, like, empty;
    static List<Integer> list[];
    static List<int []> condition1, condition2;
    
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
    static int [] score = {0,1,10,100,1000};
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        
        N = Integer.parseInt(br.readLine());
        
        seat = new int[N][N];
        
        list = new ArrayList[N*N+1];
        
        for(int i=1;i<N*N+1;i++) list[i] = new ArrayList<>();
        
        for(int i=0;i<N*N;i++) {
            st = new StringTokenizer(br.readLine());
            int student = Integer.parseInt(st.nextToken());
            for(int j=0;j<4;j++) {
                list[student].add(Integer.parseInt(st.nextToken()));
            }
            findSeat(student);
        }
        
        cal();
        System.out.println(answer);
 
    }
    
    
    public static void findSeat(int student) {
        like = new int[N][N];
        empty = new int[N][N];
        condition1 = new ArrayList<>();
        condition2 = new ArrayList<>();
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(seat[i][j]==0) {
                    for(int d=0;d<4;d++) {
                        int nx = i+dx[d];
                        int ny = j+dy[d];
                        if(range(nx,ny)) {
                            if(list[student].contains(seat[nx][ny])) { //인접한 좋아하는 학생
                                like[i][j]++;
                            }
                            else if(seat[nx][ny]==0) { //인접한 빈 곳
                                empty[i][j]++;
                            }
                        }
                    }
                }
            }
        }
        
        int max=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(seat[i][j]==0) {
                    if(max<like[i][j]) {
                        max = like[i][j];
                        condition1.clear();
                        condition1.add(new int[] {i,j});
                    }else if(max==like[i][j]) {
                        condition1.add(new int[] {i,j});
                    }
                }
            }
        }
       //condition1 리스트 사이즈가 1인경우 조건1충족
        if(condition1.size()==1) seat[condition1.get(0)[0]][condition1.get(0)[1]] = student;
        else { //아닌 경우 조건 2,3고려
            max =0;
            for(int i=0;i<condition1.size();i++) {
                int [] temp = condition1.get(i);
                
                if(max<empty[temp[0]][temp[1]]) {
                    max = empty[temp[0]][temp[1]];
                    condition2.clear();
                    condition2.add(new int[] {temp[0],temp[1]});
                }else if(max==empty[temp[0]][temp[1]]) {
                    condition2.add(new int[] {temp[0],temp[1]});
                }
            }
            seat[condition2.get(0)[0]][condition2.get(0)[1]]= student;    
        }
        
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<N;
    }
 
    public static void cal() {
        int count=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                count=0;
                for(int d=0;d<4;d++) {
                    int nx = i+dx[d];
                    int ny = j+dy[d];
                    
                    if(range(nx,ny) && list[seat[i][j]].contains(seat[nx][ny])) count++;
                }
                answer+=score[count];
            }
        }
    }
}
 cs

 

 

'문제 > 백준' 카테고리의 다른 글

백준 1417번 국회의원 선거 [JAVA]  (0) 2022.06.06
백준 1918번 후위 표기식 [JAVA]  (0) 2022.04.26
백준 17143번 낚시왕 [JAVA]  (0) 2021.12.01
백준 13549번 숨바꼭질3 [JAVA]  (0) 2021.11.23
백준 3085번 사탕 게임 [JAVA]  (0) 2021.11.18
 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.

www.acmicpc.net

 

풀이 방법

이 낚시왕 문제는 다시 풀어본 문제라 확실히 전보다는 코드가 더 깔끔해진 것 같습니다!

 

먼저,

1. 사람을 오른쪽으로 한 칸 움직인 뒤, 땅과 가장 가까운 상어를 하나 잡기

2. 격자판에 있는 상어를 움직이기

로 풀면 되는 시뮬레이션 문제였습니다.

 

저는 객체 배열을 하나 생성해 해당 위치에 상어의 정보를 넣어주었습니다. 상어가 움직일 때는 새로운 배열에 저장해 놓고 다 움직이고 난 뒤, 원래 배열에 복사해 넣는 방식으로 구현했습니다.

(상어 움직이는 것을 for문이 아닌 mod로 한다면 더 빨라질 것 같습니다!)

 

 

<예전 풀이>

 

백준 17143번 낚시왕 [JAVA]

문제 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸

javaju.tistory.com

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_17143_낚시왕 {
    
    static class shark {
        int s,d,z;
 
        public shark(int s, int d, int z) {
            super();
            this.s = s;
            this.d = d;
            this.z = z;
        }
        
    }
    
    static int R,C,M, answer=0;
    static shark [][] map, copy;
    static int [] dx = {0,-1,1,0,0};
    static int [] dy = {0,0,0,1,-1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken()); //상어 수
        
        map = new shark[R][C];
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            
            int r = Integer.parseInt(st.nextToken())-1; 
            int c = Integer.parseInt(st.nextToken())-1;
            int s = Integer.parseInt(st.nextToken()); //속력
            int d = Integer.parseInt(st.nextToken()); //이동 방향
            int z = Integer.parseInt(st.nextToken()); //크기
            
            map[r][c] = new shark(s,d,z);
        }
        
        for(int i=0;i<C;i++) {
            //1.한칸 이동해서 땅과 가장 가까운 상어 잡아먹기
            movePerson(i);
            
            //2.상어 이동하기
            moveShark();
        }
        
        System.out.println(answer);
    }
    
    public static void movePerson(int y) {
        for(int i=0;i<R;i++) {
            if(map[i][y]!=null) {
                answer+=map[i][y].z;
                map[i][y]=null;
                return;
            }
        }
    }
    
    public static void moveShark() {
        copy = new shark[R][C];
        
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                if(map[i][j]!=null) { //상어 움직이자!
                    shark temp = map[i][j];
                    map[i][j] = null;
                    
                    int nx=i,ny=j;
                    for(int k=0;k<temp.s;k++) {
                        if(temp.d==1 && nx==0) temp.d=2;
                        else if(temp.d==2 && nx==R-1) temp.d=1;
                        else if(temp.d==3 && ny==C-1) temp.d=4;
                        else if(temp.d==4 && ny==0) temp.d=3;
                        
                        nx+=dx[temp.d];
                        ny+=dy[temp.d];
                    }
                    
                    if(copy[nx][ny]==null || copy[nx][ny].z<temp.z ) {
                        copy[nx][ny] = temp;
                    }
                }
            }
        }
        map = copy;
    }
}
 cs

 

 

'문제 > 백준' 카테고리의 다른 글

백준 1918번 후위 표기식 [JAVA]  (0) 2022.04.26
백준 21608 상어 초등학교 [JAVA]  (0) 2021.12.01
백준 13549번 숨바꼭질3 [JAVA]  (0) 2021.11.23
백준 3085번 사탕 게임 [JAVA]  (0) 2021.11.18
백준 11724번 연결 요소의 개수_Union Find [JAVA]  (0) 2021.11.17
 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

풀이 방법

N의 위치에서 K위치까지 가는데 걸리는 최소의 시간을 구하는 문제였습니다.

 

저는 BFS알고리즘을 사용하여 문제를 풀었으며,

for문을 이용해 순간 이동할 때와 걸을 경우를 구분하여 우선순위 큐에 넣어주었습니다. 방문을 확인하는 visited배열을 이용하여 해당 이동한 곳이 방문한 곳이 아닐 경우에만 이동할 수 있도록 구현했습니다. 우선순위 큐로 움직인 횟수가 가장 작은 것부터 움직일 수 있도록 했기 때문에 만약 현재 위치가 동생이 있는 곳이라면 시간을 출력해주고 반복문을 종료해주었습니다. 

 

코드

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
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 Main_BJ_13549_숨바꼭질3 {
    
    static class info implements Comparable<info>{
        int position, time;
 
        public info(int position, int time) {
            super();
            this.position = position;
            this.time = time;
        }
 
        @Override
        public int compareTo(info o) {
            return this.time-o.time;
        }
    }
    
    static int N,K;
    static boolean [] visited;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        visited = new boolean[100001];
        
        move();
    }
    
    public static void move() {
        Queue<info> pq = new LinkedList<>();
        
        pq.add(new info(N,0));
        
        while(!pq.isEmpty()) {
            info temp = pq.poll();
            
            if(temp.position == K) {
                System.out.println(temp.time);
                return;
            }
            
            int nx = 0;
            for(int i=0;i<3;i++) {
                if(i==0) nx = temp.position*2;
                else if(i==1) nx = temp.position-1;
                else if(i==2) nx = temp.position+1;
                
                if(range(nx) && !visited[nx]) {
                    if(i==1 || i==2) pq.add(new info(nx, temp.time+1));
                    else pq.add(new info(nx, temp.time));
                    visited[nx] = true;
                }
            }
        }
    }
    
    public static boolean range(int x) {
        return x>=0 && x<visited.length;
    }
 
}
 cs

 

 

'문제 > 백준' 카테고리의 다른 글

백준 21608 상어 초등학교 [JAVA]  (0) 2021.12.01
백준 17143번 낚시왕 [JAVA]  (0) 2021.12.01
백준 3085번 사탕 게임 [JAVA]  (0) 2021.11.18
백준 11724번 연결 요소의 개수_Union Find [JAVA]  (0) 2021.11.17
백준 1753 최단경로 [JAVA]  (0) 2021.11.06
 

3085번: 사탕 게임

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

www.acmicpc.net

 

풀이 방법

배열 전체를 돌면서 기준이 되는 사탕과 인접한 사탕의 색깔이 다른 경우 위치를 교환해, 행과 열을 확인하여 최대 먹을 수 있는 사탕을 계산해 주었습니다.

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main_BJ_3085_사탕게임 {
    
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
    
    static int N, max=0;
    static char [][] map;
    
    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];
        
        for(int i=0;i<N;i++) {
            String line = br.readLine();
            for(int j=0;j<N;j++) {
                map[i][j] = line.charAt(j);
            }
        }
        
        candy();
        System.out.println(max);
    }
    
    public static void candy() {
        for(int x=0;x<N;x++) {
            for(int y=0;y<N;y++) {
                
                for(int d=0;d<4;d++) { // 상 하 좌 우 인접한곳
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    
                    if(range(nx,ny) && map[x][y]!=map[nx][ny]) {
                        char temp = map[x][y];
                        map[x][y] = map[nx][ny];
                        map[nx][ny] = temp;
                        
                        check(); //먹을 수 있는 사탕 개수 확인
                        
                        temp = map[x][y];
                        map[x][y] = map[nx][ny];
                        map[nx][ny] = temp;
                    }
                }
            }
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<N;
    }
    
    public static void check() {
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                count(i,j);
            }
        }    
    }
    
    public static void count(int x, int y) {
        
        int yy=y, xx=x, row=1, col=1;
        //연속된 행
        for(int i=y+1;i<N;i++) {
            if(map[x][yy]==map[x][i]) {
                row++;
                yy = i; 
            }else break;
        }
        
        //연속된 
        for(int i=x+1;i<N;i++) {
            if(map[xx][y]==map[i][y]) {
                col++;
                xx = i;
            }else break;
        }
        
        int result = Math.max(row, col);
        max = Math.max(result, max);
    }
 
}
 cs
 
 
  

 

'문제 > 백준' 카테고리의 다른 글

백준 17143번 낚시왕 [JAVA]  (0) 2021.12.01
백준 13549번 숨바꼭질3 [JAVA]  (0) 2021.11.23
백준 11724번 연결 요소의 개수_Union Find [JAVA]  (0) 2021.11.17
백준 1753 최단경로 [JAVA]  (0) 2021.11.06
백준 15686 치킨 배달 [JAVA]  (0) 2021.10.23
 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주

www.acmicpc.net

 

풀이 과정

방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 문제였습니다.

 

저는 Union Find 알고리즘을 이용하여 문제를 풀었으며,

각각의 간선의 부모(Find)가 다른 경우 Union 메서드를 통해 간선을 연결시켜 주었습니다.

 

M번의 반복문이 끝난 뒤, HashSet을 이용해 연결요소의 개수를 구해주었습니다.

 

[같은 문제의 배열 풀이방법]

 

백준 11724번 연결 요소의 개수 [JAVA]

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N

javaju.tistory.com

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main_BJ_11724_연결요소의개수 {
    
    static int N,M;
    static int [] parents;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashSet<Integer> hs = new HashSet<>();
        
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        parents = new int[N+1];
        
        for(int i=1;i<parents.length;i++) parents[i] = i;
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            if(find(u)!=find(v)) union(u,v);
                
        }
        
        for(int i=1;i<parents.length;i++) {
            hs.add(find(parents[i]));
        }
        
        System.out.println(hs.size());
    }
    
    public static void union(int a,int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        
        if(aRoot>bRoot) parents[aRoot] = bRoot;
        else parents[bRoot] = aRoot;
    }
    
    public static int find(int a) {
        if(parents[a]==a) return a;
        return parents[a] = find(parents[a]);
    }
 
}
 cs

 

'문제 > 백준' 카테고리의 다른 글

백준 13549번 숨바꼭질3 [JAVA]  (0) 2021.11.23
백준 3085번 사탕 게임 [JAVA]  (0) 2021.11.18
백준 1753 최단경로 [JAVA]  (0) 2021.11.06
백준 15686 치킨 배달 [JAVA]  (0) 2021.10.23
백준 1406번 에디터 [JAVA]  (0) 2021.10.20
 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가

www.acmicpc.net

 

풀이 방법

i번 정점으로의 최단 경로를 구하는 문제였습니다.

 

해당 간선의 정보를 list[]에 넣어주었습니다. 우선순위 큐를 이용해 가중치가 작은 간선부터 탐색을 시작했습니다.

시작점에서 연결된 간선 중 아직 방문하지 않았으며 해당 정점으로 바로가는 것보다 다른 곳을 거쳐 도착하는 거리가 더 짧으면 distance 배열에 거리를 변경해주고 간선 정보를 큐에에 넣어 이와 같은 과정을 반복해주었습니다.

 

 

[아래 링크는 다른 방법으로 푼 1753번 최단경로]

 

백준 1753번 최단경로 [JAVA]

문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개

javaju.tistory.com

[다른 방법으로 푼 1753번 최단경로]

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_BJ_1753_최단경로_PQ {
    
    static class info implements Comparable<info>{
        int end, weight;
 
        public info(int end, int weight) {
            super();
            this.end = end;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(info o) {
            return this.weight-o.weight;
        }
        
    }
    
    static int V,E;
    static int [] distance;
    static ArrayList<info> node[];
    static boolean [] visited;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        
        st = new StringTokenizer(br.readLine());
        
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        distance = new int[V+1];
        node = new ArrayList[V+1];
        visited = new boolean[V+1];
        
        for(int i=1;i<distance.length;i++) node[i] = new ArrayList<>();
        
        int start = Integer.parseInt(br.readLine());
        
        for(int i=1;i<distance.length;i++) distance[i] = Integer.MAX_VALUE;
        distance[start] = 0;
        
        for(int i=0;i<E;i++) {
            st = new StringTokenizer(br.readLine());
            
            int go = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            
            node[go].add(new info(end,value));
        }
        
        dijkstra(start);
        
        for(int i=1;i<distance.length;i++) {
            if(distance[i]==Integer.MAX_VALUE) sb.append("INF\n");
            else sb.append(distance[i]+"\n");
        }
        System.out.println(sb.toString());
 
    }
    
    public static void dijkstra(int start) {
        PriorityQueue<info> pq = new PriorityQueue<>();
        pq.add(new info(start,0));
        
        while(!pq.isEmpty()) {
            info temp = pq.poll();
            
            if(!visited[temp.end]) {
                for(info item : node[temp.end]) {
                    if(distance[item.end]> distance[temp.end]+item.weight) {
                        distance[item.end]=distance[temp.end]+item.weight;
                        pq.add(new info(item.end,distance[item.end]));
                    }
                }
                visited[temp.end] = true;
            }
        }
        
    }
 
}
 cs

 

'문제 > 백준' 카테고리의 다른 글

백준 3085번 사탕 게임 [JAVA]  (0) 2021.11.18
백준 11724번 연결 요소의 개수_Union Find [JAVA]  (0) 2021.11.17
백준 15686 치킨 배달 [JAVA]  (0) 2021.10.23
백준 1406번 에디터 [JAVA]  (0) 2021.10.20
백준 8972번 미친 아두이노 [JAVA]  (0) 2021.10.19
 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

풀이 방법

치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최솟값을 구하는 문제였습니다.

 

도시의 정보가 주어질 때,

1인 경우에는 home 리스트에 2인 경우에는 chicken 리스트에 위치 정보를 넣어주었습니다.

 

최대 M개의 치킨 집을 선택하기 위해서 조합을 이용했고,

M개를 선택했을 때 check() 메서드에서 집의 위치로부터 치킨집들의 최소 거리를 구해주었습니다.

 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main_BJ_15686_치킨배달 {
    
    static class info{
        int x, y;
 
        public info(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
    }
    
    static int N,M, min=Integer.MAX_VALUE;
    static int [][] map;
    
    static ArrayList<info> chicken = new ArrayList<>();
    static ArrayList<info> choice = new ArrayList<>();
    static ArrayList<info> home = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][N];
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==2) chicken.add(new info(i,j));
                else if(map[i][j]==1) home.add(new info(i,j));
            }
        }
        
        comb(0,0);
        System.out.println(min);
    }
    
    public static void comb(int cnt, int start) {
        if(cnt==M) {
            check();
            return;
        }
        
        for(int i=start;i<chicken.size();i++) {
            choice.add(new info(chicken.get(i).x, chicken.get(i).y));
            comb(cnt+1, i+1);
            choice.remove(choice.size()-1);
        }
    }
    
    public static void check() {
        int distance, sum=0;
        for(int i=0;i<home.size();i++) {
            distance=Integer.MAX_VALUE;
            for(int j=0;j<choice.size();j++) {
                distance = Math.min(distance, Math.abs(home.get(i).x-choice.get(j).x)+Math.abs(home.get(i).y-choice.get(j).y));
            }
            sum+=distance;
        }
        
        min = Math.min(min, sum);
    }
 
}
 cs

 

'문제 > 백준' 카테고리의 다른 글

백준 11724번 연결 요소의 개수_Union Find [JAVA]  (0) 2021.11.17
백준 1753 최단경로 [JAVA]  (0) 2021.11.06
백준 1406번 에디터 [JAVA]  (0) 2021.10.20
백준 8972번 미친 아두이노 [JAVA]  (0) 2021.10.19
백준 23056번 참가자 명단 [JAVA]  (0) 2021.10.17
 

1406번: 에디터

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수

www.acmicpc.net

 

풀이 방법

해당 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력하는 문제였습니다.

 

저는 초기 편집기에 입력되어 있는 문자열을 list에 넣고 list의 사이즈를 index로 해당 커서의 위치를 변경해주면서 명령어를 수행해주었습니다. 하지만 채점 결과 시간 초과가 발생했고 이 문제를 해결하기 위해 질문게시판과 블로그를 찾아봤습니다.

 

이 문제는 삽입/삭제가 빈번하게 일어나는데 빠른 처리시간을 요구하고 있었습니다. 그래서 더 빠르게 현재 위치를 찾으면서 삽입/삭제를 처리할 수 있는 방법을 찾았습니다.

 

바로 ListIterator을 사용하는 것이었습니다.

 

ListIterator는 컬렉션 요소에 접근할 때 한 방향으로만 이동하는 것이 아니라 양방으로 이동할 수 있습니다. 그래서 커서를 앞 뒤로 움직일 수 있도록 해당 메서드를 이용하여 커서를 움직이며 문제를 해결해나갔습니다.

 

ListIterator를 이용해 문제를 풀었지만 채점 결과 또 시간 초과가 났고,

마지막에 편집기에 입력되어있는 문자열을 출력해주기 위해 사용된 기존 for문을 향상된 for문을 이용하여 출력하니 정답을 맞출 수 있었습니다. 

 

코드

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
 
public class Main_BJ_1406_에디터 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        LinkedList<Character> list = new LinkedList<>();
        
        String command = br.readLine();
        
        for(int i=0;i<command.length();i++) {
            list.add(command.charAt(i));
        }
        
        ListIterator<Character> liter = list.listIterator();
        while (liter.hasNext()) {
            liter.next(); 
        }
 
        int M = Integer.parseInt(br.readLine());
        
        for(int i=0;i<M;i++) {
            String str = br.readLine();
            char com = str.charAt(0);
            if(com=='L') {
                if(liter.hasPrevious()) liter.previous();
            }
            else if(com=='D') {
                if(liter.hasNext()) liter.next();
            }
            else if(com=='B') {
                if(liter.hasPrevious()) { 
                    liter.previous(); 
                    liter.remove(); 
                }
            }
            else if(com=='P') {
                liter.add(str.charAt(2));
            }
        }
        
        for (char c : list) { 
            sb.append(c);
        } 
        
        System.out.println(sb.toString());
    }
 
}
 cs

 

 

'문제 > 백준' 카테고리의 다른 글

백준 1753 최단경로 [JAVA]  (0) 2021.11.06
백준 15686 치킨 배달 [JAVA]  (0) 2021.10.23
백준 8972번 미친 아두이노 [JAVA]  (0) 2021.10.19
백준 23056번 참가자 명단 [JAVA]  (0) 2021.10.17
백준 8911번 거북이 [JAVA]  (0) 2021.10.13

+ Recent posts

티스토리툴바