728x90

문제풀이

 

알파벳을 임의의 숫자라고했을때 이 숫자들의 합이 최대로 나올수 있도록 알파벳에 숫자를 부여해서 최대값을 구하는 문제입니다.

 

최대의 숫자가 나오기 위해서는 자릿수가 높은 알파벳에 큰 숫자를 부여하면 됩니다.

 

숫자배열 26개 (알파벳의 개수, 어떤 알파벳이 나올지 모르므로 26개로 설정)에

모든 배열을 탐색하면서 몇번째 자리의수가 몇개 나오는지 저장한다.

 

ex) 2

AAA

AAA 

 

다음과 같이 입력을 받을 경우 arr[0]에 222가 저장된다.

 

ex) 2

ABC

DEF

 

다음과 같이 입력을 받은 경우

arr[0] = 100, arr[1] = 10, arr[2] = 1, arr[3] = 100, arr[4] = 10, arr[5] = 1 가 저장된다.

 

이때 arr를 내림차순으로 정렬하여 9부터 숫자를 부여하여 총 합을 더하면 최대값을 구할 수 있다.

 

소스코드

 

import java.io.*;
import java.util.*;
class Main{
static int n;
static Integer[] arr;
public static void main(String[] args) throws IOException, Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new Integer[26];
Arrays.fill(arr, 0);
for(int i=0;i<n;i++)
{
char[] input = br.readLine().toCharArray();
int now = 1;
for(int j=input.length-1; j>=0; j--)
{
arr[input[j] - 'A'] += Integer.valueOf(now);
now *= 10;
}
}
Arrays.sort(arr, Collections.reverseOrder());
int num = 9;
int sum = 0;
for(int i=0;i<10;i++)
{
sum += arr[i] * num--;
}
System.out.println(sum);
}
}
view raw 1339.java hosted with ❤ by GitHub
LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Tree] BOJ 10610번, 트리의 지름(JAVA)  (0) 2021.11.04
[Sort] BOJ 10610번, 30(JAVA)  (0) 2021.11.01
[Sort] BOJ 1181번, 단어 정렬(JAVA)  (2) 2021.10.31
[Topology Sort] BOJ 2252번, 줄 세우기(JAVA)  (0) 2021.10.29
[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
SnowMan개발자지만 개발자 지망생의 블로그입니다.
728x90

문제풀이

 

어떠한 노드에서 다른 노드까지의 최대 거리를 출력하는 문제이다.

우선 데이터를 어떻게 저장할것인가가 핵심 포인트이다.

List<Node>[] nodes 배열을 선언해서 입력으로 들어오는 모든 데이터를 연결하였다.

 

1. 임의의 노드에서 최대 거리인 노드의 위치를 기록한다(max_idx)

 

2. 1번에서 정해진 max_idx 에서 최대 거리의 노드를 찾는다.

 

소스코드

 

import java.io.*;
import java.util.*;
public class Main {
static int n;
static List<Node>[] nodes;
static boolean[] visited;
static int max, max_idx;
public static void main(String[] args) throws Exception, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
nodes = new ArrayList[n+1];
for(int i=0;i<=n;i++)
nodes[i] = new ArrayList<>();
for(int i=0;i<n-1;i++)
{
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
nodes[a].add(new Node(b,c));
nodes[b].add(new Node(a,c));
}
visited = new boolean[n+1];
visited[1] = true;
dfs(1,0);
visited = new boolean[n+1];
visited[max_idx] = true;
dfs(max_idx,0);
System.out.println(max);
}
static void dfs(int idx, int dist)
{
if(max < dist)
{
max = dist;
max_idx = idx;
}
for(Node next : nodes[idx])
{
if(!visited[next.data])
{
visited[next.data] = true;
dfs(next.data, dist + next.dist);
}
}
}
}
class Node{
int data;
int dist;
Node(int data, int dist)
{
this.data = data;
this.dist = dist;
}
}
view raw test.java hosted with ❤ by GitHub

https://www.acmicpc.net/problem/1967

 

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Greedy] BOJ 1339번, 단어 수학(JAVA)  (0) 2021.11.08
[Sort] BOJ 10610번, 30(JAVA)  (0) 2021.11.01
[Sort] BOJ 1181번, 단어 정렬(JAVA)  (2) 2021.10.31
[Topology Sort] BOJ 2252번, 줄 세우기(JAVA)  (0) 2021.10.29
[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
SnowMan개발자지만 개발자 지망생의 블로그입니다.
728x90

문제풀이

 

두가지 접근방법

1. DFS 를 이용한 전체 탐색

 - 처음에 시도했던 방법이다.  메모리 초과가 나와서 역시나했나다..

   그 이유는 최대 10^5 개의 숫자를 DFS로 탐색하려면 엄청난 메모리가 사용될거라 생각했다.

   이 방법이 틀린줄 알면서 풀어본 이유는 대부분의 코딩테스트는 정수론 문제는 거의 출제하지 않는것 같기 때문이다.

   

2. 정수론을 이용한 정렬

 - 문제에서 주어지는 30 이란 숫자에서 생각해낸 방법이다.

   다른분들의 풀이를 보면서 참고하였다.

 

1) 우선 3의 배수의 특징은 각 자리수의 합이 3의 배수라는 점이 있다.

 

2) 우리는 30의 배수를 찾아야 하므로 입력받은 숫자를 정렬했을때 처음에 0이 오면 된다.

 

3) 두 가지 조건을 이용하여  30의 배수인지 아닌지 찾았다.

 

 

소스코드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
import java.io.*;
import java.util.*;
 
public class Main {
    static int n,k;
    static List<Integer> list = new ArrayList<>();
    static int ans = -1;
    static boolean[] selected;
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        String num = br.readLine();
        selected = new boolean[num.length()];
        dfs(0, num, "");
        
        System.out.println(ans);
    }
    static void dfs(int depth, String num, String source)
    {
        if(depth == num.length())
        {
            int k = Integer.parseInt(source);
            if(k >= 30 && k%30 == 0)
            {
                ans = Math.max(ans, k);
            }
            return;
        }
        for(int i=0;i<num.length();i++)
        {
            if(selected[i]) continue;
            selected[i] = true;
            dfs(depth+1, num, source + num.charAt(i));
            selected[i] = false;
        }
    }
}
 
 cs

 

소스코드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
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        String nums = br.readLine();
        int[] num = new int[nums.length()];
        
        int sum = 0;
        for(int i=0;i<num.length;i++)
        {
            num[i] = nums.charAt(i) - '0';
            sum += num[i];
        }
        
        Arrays.sort(num);
        
        if(sum % 3 == 0 && num[0] == 0)
        {
            for(int i=0;i<num.length;i++)
            {
                System.out.print(num[num.length-i-1]);
            }
        }
        else
            System.out.println(-1);
    }
}
 
 cs

https://www.acmicpc.net/problem/10610

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Greedy] BOJ 1339번, 단어 수학(JAVA)  (0) 2021.11.08
[Tree] BOJ 10610번, 트리의 지름(JAVA)  (0) 2021.11.04
[Sort] BOJ 1181번, 단어 정렬(JAVA)  (2) 2021.10.31
[Topology Sort] BOJ 2252번, 줄 세우기(JAVA)  (0) 2021.10.29
[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
SnowMan개발자지만 개발자 지망생의 블로그입니다.
728x90

문제풀이

 

이번 문제는 정렬 알고리즘 문제입니다.

입력으로 들어오는 문자열을 주어진 조건에 맞게 정렬하는 방법에 대해 알아보고자 합니다.

코딩테스트에서 정렬만을 단독으로 물어보는 문제는 거의 출제되지 않고 주로 정렬을 사용해서 어떤 다른것을 해라~

이런식으로 주어지기 때문에 단순 정렬이 아닌 길이순, 사전순, 이나 사용자 클래스를 만들어서 정렬 과같은 방법을 모두 알 익혀두어야 합니다. 

 

문제를 풀때 정렬을 직접 구현해서 사용해도 되지만 Collection.sort(), Arrays.sort()를 사용하는것이 시간상 더 효율적이라고 생각합니다.

 

1. sort 함수 호출할때 정렬 방법 선택하기

 

2. 사용자 정의 클래스를 만들어서 toCompare 함수 override 하기 

 

다음의 두 가지를 이용해서 문제를 풀어보겠습니다.

소스코드를 참고해 주세요.

 

소스코드

방법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
import java.io.*;
import java.util.*;
 
public class Main {
    static int n;
    static Map<String, Integer> map = new HashMap<>();
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++)
        {
            map.put(br.readLine(), 1);
        }
        
        String[] arr = new String[map.size()];
        int idx = 0;
        for(String key : map.keySet())
        {
            arr[idx++] = key;
        }
        
        Arrays.sort(arr, new Comparator<String>(){
            public int compare(String a, String b)
            {
                if(a.length() < b.length()) return -1;
                else if(a.length() > b.length()) return 1;
                else {
                    return a.compareTo(b);
                }
            }
        });
        for(int i=0;i<arr.length;i++)
        {
            sb.append(arr[i]).append('\n');
        }
        
        System.out.println(sb);
    }
}
 cs

방법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
import java.io.*;
import java.util.*;
 
public class Main {
    static int n;
    static Map<String, Integer> map = new HashMap<>();
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++)
        {
            map.put(br.readLine(), 1);
        }
        
        String[] arr = new String[map.size()];
        int idx = 0;
        for(String key : map.keySet())
        {
            arr[idx++] = key;
        }
        
        List<MyString> list = new ArrayList<>();
        for(int i=0;i<arr.length;i++)
        {
            list.add(new MyString(arr[i]));
        }
        
        Collections.sort(list);
        for(int i=0;i<list.size();i++)
        {
            sb.append(list.get(i).str).append('\n');
        }
        
        System.out.println(sb);
    }
}
 
class MyString implements Comparable<MyString>{
    String str;
    
    public MyString(String s)
    {
        str = s;
    }
    
    @Override
    public int compareTo(MyString mString)
    {
        if(str.length() < mString.str.length()) return -1;
        else if(str.length() > mString.str.length()) return 1;
        else{
            return str.compareTo(mString.str);
        }
    }
}
 cs

https://www.acmicpc.net/problem/1181

 

1181번: 단어 정렬

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Tree] BOJ 10610번, 트리의 지름(JAVA)  (0) 2021.11.04
[Sort] BOJ 10610번, 30(JAVA)  (0) 2021.11.01
[Topology Sort] BOJ 2252번, 줄 세우기(JAVA)  (0) 2021.10.29
[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
[BFS] BOJ 2583번, 영역 구하기(JAVA)  (0) 2021.10.28
SnowMan개발자지만 개발자 지망생의 블로그입니다.
728x90

문제풀이

 

위상정렬은 순서가 정해져있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 이다.

보통의 경우 어떤 조건을 주고 순서대로 나열하는 경우를 물어본다.

 

이 줄세우기 문제는 인적성 시험? 볼때 이런 경우일때 참,거짓을 물어보는 문제를 풀었던 기억이 난다.

알고리즘 자체는 어렵지 않은데 이 방법을 생각해내기는 어려울 것 같다.

 

다음의 유튜브를 참고 하였다.

https://www.youtube.com/watch?v=qzfeVeajuyc&t=709s 

소스코드

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
import java.util.*;
import java.io.*;
class Main{
    static int n,m;
    static int[] inDegree;
    static List<Integer>[] nodes;
    static int[] result;
    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());
        inDegree = new int[n+1];
        nodes = new ArrayList[n+1];
        result = new int[n+1];
        for(int i=1;i<=n;i++)
            nodes[i] = new ArrayList<>();
        
        for(int i=0;i<m;i++)
        {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            nodes[a].add(b);
            inDegree[b]++;
        }
            
        topologySort();
        
        for(int i=1;i<=n;i++)
        {
            System.out.print(result[i] + " ");
        }
    }
    static void topologySort()
    {
        Queue<Integer> q = new LinkedList<>();
        
        for(int i=1;i<=n;i++)
        {
            if(inDegree[i] == 0)
                q.add(i);
        }
        
        for(int i=1;i<=n;i++)
        {
            if(q.isEmpty()) break;
            
            int x = q.poll();
            result[i] = x;
            
            for(int j=0;j<nodes[x].size();j++)
            {
                int y = nodes[x].get(j);
                inDegree[y]--;
                if(inDegree[y] == 0)
                    q.add(y);
            }
        }
    }
}
 cs

https://www.acmicpc.net/problem/2252

 

2252번: 줄 세우기

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Sort] BOJ 10610번, 30(JAVA)  (0) 2021.11.01
[Sort] BOJ 1181번, 단어 정렬(JAVA)  (2) 2021.10.31
[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
[BFS] BOJ 2583번, 영역 구하기(JAVA)  (0) 2021.10.28
[BFS] BOJ 7562번, 나이트의 이동(JAVA)  (0) 2021.10.28
SnowMan개발자지만 개발자 지망생의 블로그입니다.
728x90

문제풀이

 

최소 스패닝 트리(Minimum Spanning Tree)

정점과 정점을 연결하는 간선의 가중치가 동일하지 않을 때 가중치가 작은 간선을 골라 연결한다고해서 최소 스패닝 트리라고 한다.

 

간선이 작은 순서대로 연결하고 싸이클이 생기지 않도록 연결하는 방법이다.

 

N개의 정점을 연결하는 간선의 개수는 반드시 N-1 개이다.

 

최소 스패닝 트리를 만드는 대표적인 알고리즘으로 Kruskal, Prim 이 있는데 오늘은 크루스칼 알고리즘을

이용해 해결해 보았다.

 

구현 알고리즘

1. Kruskal 알고리즘

 - 그리디한 방법을 이용한다.

 - 간선의 가중치를 오름차순으로 정렬하고

 - 정렬된 간선 리스트를 순서대로 탐색하면서 싸이클이 생겼는지 확인한다.

 

다음 유튜브를 보면 자세하게 나와있으니 한번 보면 내 설명보다 훨씬 이해가 잘된다.

https://www.youtube.com/watch?v=LQ3JHknGy8c&t=462s 

소스코드

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
import java.util.*;
import java.io.*;
class Main{
    static int n,m;
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>(){
       public int compare(Edge a, Edge b)
       {
           if(a.dist < b.dist) return -1;
           else if(a.dist > b.dist) return 1;
           else return 0;
       }
    });
    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());
        
        parent = new int[n+1];
        for(int i=1;i<=n;i++)
        {
            parent[i] = i;
        }
        
        for(int i=0;i<m;i++)
        {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            pq.add(new Edge(a,b,c));
        }
        
        int sum = 0;
        for(int i=0;i<m;i++)
        {
            Edge e = pq.poll();
            if(find(e.node1) != find(e.node2))
            {
                sum += e.dist;
                union(e.node1, e.node2);
            }
        }
        System.out.println(sum);
    }
    static int find(int x)
    {
        if(parent[x] == x) return x;
        else return parent[x] = find(parent[x]);
    }
    static void union(int x, int y)
    {
        x = find(x);
        y = find(y);
        if(y>x)
            parent[y] = x;
        else
            parent[x] = y;
    }
}
class Edge{
    int node1;
    int node2;
    int dist;
    public Edge(int node1, int node2, int dist)
    {
        this.node1 = node1;
        this.node2 = node2;
        this.dist = dist;
    }
}
 cs

https://www.acmicpc.net/problem/1197

 

1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Sort] BOJ 1181번, 단어 정렬(JAVA)  (2) 2021.10.31
[Topology Sort] BOJ 2252번, 줄 세우기(JAVA)  (0) 2021.10.29
[BFS] BOJ 2583번, 영역 구하기(JAVA)  (0) 2021.10.28
[BFS] BOJ 7562번, 나이트의 이동(JAVA)  (0) 2021.10.28
[BFS] BOJ 7569번, 토마토(JAVA)  (0) 2021.10.28
SnowMan개발자지만 개발자 지망생의 블로그입니다.
728x90

문제풀이

 

이 문제는 그래프 이론중에 좌표와 영역에 해당하는 문제로 보인다.

 

이차월 배열에서 좌표값과 해당 영역을 구하는 문제가 종종 나오는데 이러한 경우 직접 그림을 그리면서

하거나 print 문을 이용해서 찍어보면서 하면 좀 편하다.

 

위의 그림에서는 배열의 시작이 왼쪽 아래에서 시작한다.

 

하지만 우리는 왼쪽 위에서 시작해서 오른쪽아래로 탐색하는것이 편해서 그림은 수평으로 대칭이동해서 생각해 보면 편하다.

수평으로 대칭시킨 배열 상태

아래 코드에서 영역의 개수는 bfs의 호출 횟수이고

각 bfs가 호출할때 queue에서 꺼내지는 횟수가 각 영역의 넓이이다.

 

소스코드

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.util.*;
import java.io.*;
class Main{
    static int n,m,k;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int[][] map;
    static boolean[][] visited;
    static List<Integer> ans = new ArrayList<>();
    static int total;
    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());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new int[n+1][m+1];
        visited = new boolean[n+1][m+1];
        while(k-- > 0)
        {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            
            for(int i=y1;i<y2;i++)
            {
                for(int j=x1;j<x2;j++)
                {
                    map[i][j] = 1;
                }
            }
        }
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(map[i][j] == 0 && !visited[i][j])
                {
                    bfs(i,j);
                    total++;
                }
            }
        }
        Collections.sort(ans);
        sb.append(total).append('\n');
        for(int i=0;i<total;i++)
        {
            sb.append(ans.get(i)).append(' ');
        }
        System.out.println(sb);
    }
    static void bfs(int y, int x)
    {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(y,x));
        visited[y][x] = true;
        int cnt = 0;
        while(!q.isEmpty())
        {
            Pos p = q.poll();
            cnt++;
            for(int i=0;i<4;i++)
            {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];
                if(ny>=0 && nx>=0 && ny<n && nx<m)
                {
                    if(!visited[ny][nx] && map[ny][nx] == 0)
                    {
                        visited[ny][nx] = true;
                        q.add(new Pos(ny,nx));
                    }
                }
            }
        }
        ans.add(cnt);
    }
}
class Pos{
    int y,x;
    public Pos(int y, int x)
    {
        this.y = y;
        this.x = x;
    }
}
 cs

https://www.acmicpc.net/problem/2583

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Topology Sort] BOJ 2252번, 줄 세우기(JAVA)  (0) 2021.10.29
[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
[BFS] BOJ 7562번, 나이트의 이동(JAVA)  (0) 2021.10.28
[BFS] BOJ 7569번, 토마토(JAVA)  (0) 2021.10.28
[BFS] BOJ 10026번, 적록 색약(JAVA)  (0) 2021.10.28
SnowMan개발자지만 개발자 지망생의 블로그입니다.
728x90

문제풀이

 

일반적인 이차원배열에서의 이동 문제랑 다르게 이동할 수 있는 방향이 위의 그림과 같이 8가지 방향이 있다.

이때 방향백터를

static int[] dx = {-2,-2,-1,-1,1,1,2,2};
static int[] dy = {-1,1,-2,2,-2,2,-1,1};

이렇게 설정하여 무난하게 해결하였다.

이때 시작은 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.*;
import java.io.*;
class Main{
    static int n;
    static int[] dx = {-2,-2,-1,-1,1,1,2,2};
    static int[] dy = {-1,1,-2,2,-2,2,-1,1};
    static int[][] visited;
    static int ans;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int tc = Integer.parseInt(br.readLine());
        while(tc-- > 0)
        {
            n = Integer.parseInt(br.readLine());
            visited = new int[n][n];
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            Pos start = new Pos(a,b);
            
            st = new StringTokenizer(br.readLine(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            Pos dest = new Pos(a,b);
        
           bfs(start,dest);
            System.out.println(ans-1);
        }
    }
    static void bfs(Pos start, Pos dest)
    {
        Queue<Pos> q = new LinkedList<>();
        q.add(start);
        visited[start.y][start.x] = 1;
        while(!q.isEmpty())
        {
            Pos p = q.poll();
            if(p.y == dest.y && p.x == dest.x)
            {
                ans = visited[p.y][p.x];
                break;
            }
            for(int i=0;i<8;i++)
            {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];
                if(ny>=0 && nx>=0 && ny<n && nx<n)
                {
                    if(visited[ny][nx] == 0)
                    {
                        visited[ny][nx] = visited[p.y][p.x] + 1;
                        q.add(new Pos(ny,nx));
                    }
                }
            }
        }
    }
}
class Pos{
    int y,x;
    public Pos(int y, int x)
    {
        this.y = y;
        this.x = x;
    }
}
 cs

https://www.acmicpc.net/problem/7562

 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
[BFS] BOJ 2583번, 영역 구하기(JAVA)  (0) 2021.10.28
[BFS] BOJ 7569번, 토마토(JAVA)  (0) 2021.10.28
[BFS] BOJ 10026번, 적록 색약(JAVA)  (0) 2021.10.28
[DFS] BOJ 1987번, 알파벳(JAVA)  (0) 2021.10.28
SnowMan개발자지만 개발자 지망생의 블로그입니다.

+ Recent posts

티스토리툴바