[백준/Gold IV] 2차원 배열의 연산 | 여행가자
문제
초기 3×3 크기의 2차원 배열 A가 주어지고, 매 초마다 배열에 R 또는 C 연산을 적용한다.
어떤 연산을 적용할지는 현재 배열의 행과 열의 크기로 결정되는데, 행의 개수가 열의 개수보다 크거나 같으면 R 연산, 작으면 C 연산을 수행한다.
- R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
- C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.
목표는 A[r][c]의 값이 k가 되는 최소 시간을 구하는 것이다. 0초(초기 상태)부터 100초까지 체크하며, 100초 내에 조건을 만족하지 못하면 -1을 출력한다.
자세한 사항은 아래 문제 URL을 참조
전체적인 흐름
map[][]의 상태에 따라 R연산 또는 C연산을 수행한다.- 각 연산에 맞게 1차원 배열의 값을 추출한다.
- HashMap을 정렬한다.
- 추출한 1차원 배열의 값을 초기 값
0으로 초기화한다. - 정렬된 HashMap의 값을 배열에 새로 쓰고 가장 긴 hashMap을 연산의 결과로 return 한다.
- 이를 100번동안 반복하며 값을 찾는다.
해당 문제를 풀면서 가장 신경쓰였던 점은 HashMap의 적절한 사용이다.
HashMap을 사용하면서 어떻게 정렬 요구사항을 달성하는것과 HashMap의 Key의 유무에 따라 어떤식으로 값을 초기화 할지 막혔던 부분이 있어 해당 부분을 적어보았다.
HashMap 정렬하기
해당 문제도 마찬가지로 특정 조건일 때 정렬 방식에 대해 조금 신경을 써야한다.
R/C 연산은 행/열의 각 숫자를 (등장횟수 → 숫자) 오름차순으로 정렬해서 (숫자, 등장횟수) 쌍으로 다시 배열에 넣어야하는데, 등장 횟수 자체는 HashMap을 사용하면 될듯 하지만 문제는 HashMap의 정렬이였다.
정렬을 하기 위해 사용한 것은 Map.Entrty라는 객체로 기존 HashMap의 .entrySet()을 사용하여 Key-Value 쌍을 객체로 뽑아낼 수 있다.
만약 HashMap에 아래와 같이 넣는다고 가정하면
1
2
hashmap.put(3, 1); // 3이 1번
hashmap.put(1, 2); // 1이 2번
.new ArrayList<>(map.entrySet())을 통해 Key-Value 쌍 객체로 추출하고, 이 객체를 List에 넣는다.
Map.Entrty를 통해 List에 추가된 상태
1
[ Map.Entry{key=3, value=1}, Map.Entry{key=1, value=2} ]
List 자료구조 이기에 정렬이 가능하다. .sort()를 통해 문제의 요구사항 기반으로 정렬을 진행한다.
1
2
3
4
5
6
7
// Value 또는 Key를 기반으로 오름차순으로 정렬
mapList.sort( (a, b) -> {
if (Objects.equals(a.getValue(), b.getValue())) {
return a.getKey() - b.getKey();
}
return a.getValue() - b.getValue();
});
HashMap 값 넣기
HashMap을 사용할 때 Key의 유무에 따라 아래와 같은 코드를 작성하였다.
1
2
3
4
if (!hashmap.containsKey(num))
hashmap.put(num, 1);
else
hashmap.put(num, hashmap.get(num) + 1);
이걸 merge() 메소드를 사용하면 아래와 같이 한줄로 작성 가능하다.
1
hashmap.merge(num, 1, Integer::sum);
- 첫번째 인자 -> key
- 두번째 인자 -> 추가될 Value 값
- 세번째 인자 -> Value가 있다면 어떤 작업을 수행할지?
merge() 메소드의 내부 Java 로직은 아래와 같다.
1
2
3
4
5
6
7
8
9
public V merge(K key, V value, BiFunction<V, V, V> remappingFunction) {
V oldValue = get(key);
V newValue = value;
if (oldValue != null)
remappingFunction.apply(oldValue, newValue);
else
put(key, value);
}
remappingFunction에 Integer::sum 은 만약 이미 Map에 Key에 해당하는 Value가 있을 경우 어떤 로직을 수행할지를 지정하는데,
Integer::sum은 (a, b) -> a + b와 같은 의미로 기존 oldValue에 newValue를 더하는 로직(함수)을 지정할 수 있다.
위의 로직을 종합하여 아래 코드를 통해 문제를 통과하였다.
전체 코드
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
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int r, c, k;
int[][] map = new int[100][100];
// 입력
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken()) - 1;
c = Integer.parseInt(st.nextToken()) - 1;
k = Integer.parseInt(st.nextToken());
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int y = 3, x = 3, ans = -1;
for (int i = 0; i <= 100; i++) {
if (map[r][c] == k) {
ans = i;
break;
}
if (y >= x)
x = rSort(map, y, x);
else
y = cSort(map, y, x);
}
System.out.println(ans);
}
public static int rSort(int[][] map, int y, int x) {
int maxSize = 0;
for (int i = 0; i < y; i++) {
HashMap<Integer, Integer> hashmap = new HashMap<>();
// 기존 요소 x축 추출
for (int j = 0; j < x; j++) {
int num = map[i][j];
if (num == 0) continue;
hashmap.merge(num, 1, Integer::sum);
}
List<Integer> list = mapSort(hashmap);
// 초기화 후 값 넣기
Arrays.fill(map[i], 0);
int size = Math.min(list.size(), 100);
for (int j = 0; j < size; j++) {
map[i][j] = list.get(j);
}
maxSize = Math.max(maxSize, Math.min(list.size(), 100));
}
return maxSize;
}
public static int cSort(int[][] map, int y, int x) {
int maxSize = 0;
for (int i = 0; i < x; i++) {
HashMap<Integer, Integer> hashmap = new HashMap<>();
// 기존 요소 y축 추출
for (int j = 0; j < y; j++) {
int num = map[j][i];
if (num == 0) continue;
hashmap.merge(num, 1, Integer::sum);
}
List<Integer> list = mapSort(hashmap);
// 초기화 후 값 넣기
for (int k = 0; k < 100; k++)
map[k][i] = 0;
int size = Math.min(list.size(), 100);
for (int j = 0; j < size; j++) {
map[i][j] = list.get(j);
}
maxSize = Math.max(maxSize, Math.min(list.size(), 100));
}
return maxSize;
}
// Map을 정렬된 List로 반환
private static List<Integer> mapSort(HashMap<Integer, Integer> map) {
List<Integer> list = new ArrayList<>();
// Map의 요소들을 List로 담는다.
List<Map.Entry<Integer, Integer>> mapList = new ArrayList<>(map.entrySet());
// Value 또는 Key를 기반으로 오름차순으로 정렬
mapList.sort( (a, b) -> {
if (Objects.equals(a.getValue(), b.getValue())) {
return a.getKey() - b.getKey();
}
return a.getValue() - b.getValue();
});
for (Map.Entry<Integer, Integer> entry : mapList) {
list.add(entry.getKey());
list.add(entry.getValue());
}
return list;
}
}
문제 정보
여행가자 - 1976
시간 제한: 2초 메모리 제한: 128MB
문제 설명
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다.
예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.
도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.
입력
- 첫 줄에 도시의 수 N이 주어진다. (N ≤ 200)
- 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. (M ≤ 1000)
- 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다.
1이면 연결된 것0이면 연결되지 않은 것
- A와 B가 연결되었으면 B와 A도 연결되어 있다.
- 마지막 줄에는 여행 계획이 주어진다.
- 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.
출력
첫 줄에 가능하면 YES, 불가능하면 NO를 출력한다.
풀이
위 문제는 Union-Find를 문제로 보인다.
각 도시를 (0부터 시작한다고 가정) parents[] 라는 배열을 생성해 root 를 저장하는 방식으로 도시의 연결을 체크할려고 한다.
초기 상태에 모든 도시의 root는 자기 자신을 가진다.
1. 초기 root 설정하기
1
parents = IntStream.rangeClosed(0, N - 1).toArray(); // 도시들의 부모 기록
IntStream.rangeClosed(0, N - 1);: 0부터 N-1까지의 정수 Stream을 생성.toArray()Stream을 배열로 변환
2. 도시의 연결을 설정하기
1
2
3
4
5
6
int root = parent(city); // 도시의 root를 기록
for (int dest = 0; dest < N; dest++) { // 해당 도시의 목적지의 root를 찾아서 갱신
if (Integer.parseInt(st.nextToken()) == 1 && root != parent(dest)) {
parents[parent(dest)] = root;
}
}
N번째 줄마다 입력을 받고 해당 입력이 1일 경우 양 도시의 root를 비교한다. 만약 root가 다르다면 목적지인 parents[parent(dest)]에 N 번째 도시를 root로 설정한다.
3. 방문가능한지 확인
1
2
boolean ans = Arrays.stream(visited).allMatch(i -> parent(i) == parent(visited[0]));
System.out.println(ans ? "YES" : "NO");
방문이 가능한지 확인할 도시 배열 visited[]를 선언 후 .allMatch를 통해 i 번째 index의 도시의 부모와 가장 최초의 visited[0]의 부모가 모두 같은지 비교한다.
전체 코드
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.IntStream;
public class Main {
static int N, M;
static int[] parents;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
parents = IntStream.rangeClosed(0, N - 1).toArray(); // 도시들의 부모 기록
for (int city = 0; city < N; city++) {
st = new StringTokenizer(br.readLine());
int root = parent(city); // 도시의 root를 기록
for (int dest = 0; dest < N; dest++) { // 해당 도시의 목적지의 root를 찾아서 갱신
if (Integer.parseInt(st.nextToken()) == 1 && city < dest && root != parent(dest)) {
parents[parent(dest)] = root;
}
}
}
st = new StringTokenizer(br.readLine());
int[] visited = new int[M];
for (int i = 0; i < M; i++) {
visited[i] = Integer.parseInt(st.nextToken()) - 1;
}
boolean ans = Arrays.stream(visited).allMatch(i -> parent(i) == parent(visited[0]));
System.out.println(ans ? "YES" : "NO");
}
public static int parent(int city) {
if (parents[city] == city) {
return city;
}
return parents[city] = parent(parents[city]); // 경로 압축
}
}