TIL/Algorithm
[BOJ] 21608번 : 상어 유치원 (G5 - Java)
Dev우키
2023. 6. 25. 15:36
반응형
문제 링크
https://www.acmicpc.net/problem/21608
특별한 알고리즘 없이 단순 구현문제였다.
주어진 조건들을 잘 구현하면 쉽게 풀 수 있을것이라 생각한다.
풀이
문제 길이가 길었을 뿐 풀이는 비교적 간단했다.
다만 구현 과정에서 중복되는 코드가 많아 체점 시간이 320ms 언저리로 나온 것 같다.
- 입력값 처리
seq배열 : 배치 순서를 담은 배열- index : 배치 순서
- 값 : 학생의 번호
students맵 : 학생 번호(key)와 좋아하는 학생(value)를 저장한다.- 인접한 칸에 위치한 좋아하는 학생을 파악하기 위해 Set의 contains를 통해 확인하고 싶었다.
N = Integer.parseInt(st.nextToken());
int[][] map = new int[N][N];
HashMap<Integer, Set<Integer>> students = new HashMap<>();
//입력 순서대로 자리에 배치한다.
int[] seq = new int[N * N + 1];
//입력 순서 저장
for (int i = 1; i <= N * N; ++i) {
st = new StringTokenizer(br.readLine());
//순서기록
seq[i] = Integer.parseInt(st.nextToken());
//좋아하는 학생 기록
HashSet<Integer> favorite = new HashSet<>();
for (int j = 0; j < 4; ++j) {
favorite.add(Integer.parseInt(st.nextToken()));
}
students.put(seq[i], favorite);
}첫 번째 학생 위치는 (2,2)에 고정
- 인접한 빈칸 4개, 행이 가장작고, 열도 가장 작기 떄문
2 번쨰 학생 부터 조건 1, 2, 3을 고려해서 탐색을 수행한다
- 조건1 : 배열 전체를 탐색하며 각 위치마다 상하좌우 인접한 칸을 검사해 가장 많을 칸을 구해 List로 만든다.
- 조건2 : 1번의 결과 List의 size가 1보다 많을 경우, 리스트 요소마다 검사해 비어있는 칸이 가장 많은 목록을 다시 List로 만든다.
- 조건3 : 2번의 결과 List의 size가 1보다 많을 경우, 행의 번호가 가장 작은칸 > 열의 번호가 가장 작은칸 순으로 정렬해 첫 번째 요소를 반환한다.
- 마지막 요소를 출력해 교실에 배치한다.
// 구현을 담당하는 메소드
private static void simulataion(int now) {
int nowStudent = seq[now];
//최적 위치를 선별하기 위한 pq
//조건1 체크 : 비어있는 칸중 좋아하는 학생이 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다
List<int[]> filter = condition1(nowStudent);
//조건2 체크 : 1의 조건을 만족하는 칸이 여러개 -> 비어있는 칸이 가장 많은 칸으로 자리 지정
if(filter.size() > 1) filter = condtion2(filter);
//조건3 체크 : 2의 조건을 만족하는 칸도 여러개 -> 행의 번호가 가장 작은칸, 열의 번호가 가장 작은칸
if(filter.size() > 1) {
int[] result = condition3(filter);
map[result[1]][result[0]] = nowStudent;
return;
}
map[filter.get(0)[1]][filter.get(0)[0]] = nowStudent;
return;
}
//조건 1을 검사하는 메소드
private static List<int[]> condition1(int nowStudent){
List<int[]> list = new ArrayList<>();
//조건1 체크 : 비어있는 칸중 좋아하는 학생이 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다
int condition1Max = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++){
if(map[i][j]!=0) continue;
int cnt = 0;
//사방탐색을 통해 인접한 칸에 좋아하는 학생이 있는지 체크
for (int k = 0; k < 4; k++) {
int nx = j + dir[k][0];
int ny = i + dir[k][1];
if (!checkRange(nx, ny)) continue;
if(students.get(nowStudent).contains(map[ny][nx])) cnt++;
}
//인접한 칸에 좋아하는 학생이 더 많을 경우 새롭게 갱신한다.
if(cnt >= condition1Max){
if(cnt > condition1Max){
condition1Max = cnt; //인접한 학생 수 최댓 값 갱신
//우선순위 큐 초기화 후 현재 위치 다시 삽입
list.clear();
}
list.add(new int[] {j, i});
}else continue; //작으면 의미없다 버려
}
}
return list;
}
//조건 2를 검사하는 메소드
private static List<int[]> condtion2(List<int[]> condition1List) {
List<int[]> list = new ArrayList<>();
int condition2Max = Integer.MIN_VALUE;
for(int[] loc : condition1List){
int emptyCnt = 0;
for(int i = 0 ; i < 4 ; ++i){
int nx = loc[0] + dir[i][0];
int ny = loc[1] + dir[i][1];
if(!checkRange(nx, ny)) continue; //좌표 유효성 체크
if(map[ny][nx]!=0) continue; //비어있는칸인지 체크
emptyCnt++;
}
//인접한 칸에 비어있는 칸이 더 많을 경우 새롭게 갱신한다.
if(emptyCnt >= condition2Max){
if(emptyCnt > condition2Max){
condition2Max = emptyCnt; //인접한 학생 수 최댓 값 갱신
//우선순위 큐 초기화 후 현재 위치 다시 삽입
list.clear();
}
list.add(new int[] {loc[0], loc[1]});
}else continue; //작으면 의미없다 버려
}
return list;
}
//조건 3을 검사하는 메소드
private static int[] condition3(List<int[]> condition2List) {
condition2List.sort((o1, o2) -> {
return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
});
return condition2List.get(0);
}- 배치가 완료 되었으면 배열 전체 탐색하면서 점수를 계산 후 출력
private static int satisfy(int x, int y) {
int cnt = -1;
//상하좌우 체크해서 좋아하는 학생이 있으면 점수를 매긴다.
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (!checkRange(nx, ny)) continue;
if (students.get(map[y][x]).contains(map[ny][nx]))
cnt++;
}
/*
학생과 인접한 칸에 앉은 좋아하는 학생 수 구하기
0명 : 0
1명 : 1
2명 : 10
3명 : 100
4명 : 1000
*/
return (int) Math.pow(10, cnt);
}풀이 링크
반응형