주어진 작업 순서에 따라 단순히 코드 구현만 하면 되는 문제다. 다만 방향을 고려하는 과정이 좀 헷갈렸는데, 로봇 청소기의 d가 나타내는 값은 시계 방향이고 회전 방향은 반시계 방향이었기 때문이다. 그래서 회전할 때 현재 방향에 3을 더하고 4로 나눈 나머지값을 활용했고, 후진을 할 때는 2를 더했다.
코드
package week9;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ14503 {
static class Pos{
int x, y, d;
public Pos(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
}
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int n, m;
static int[][] room;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
// 입력값 저장
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
room = new int[n][m];
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken()); // 0~4: 북동남서
Pos vacuum = new Pos(r, c, d);
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++)
room[i][j] = Integer.parseInt(st.nextToken());
}
// 청소기 작동
clean(vacuum);
// 청소한 칸의 개수 표시
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if(room[i][j] == 2) sum++;
System.out.println(sum);
}
private static void clean(Pos vacuum) {
while(true){
// 1번 작업
if(room[vacuum.x][vacuum.y] == 0)
room[vacuum.x][vacuum.y] = 2;
boolean needToClean = false;
// 3번 작업
for (int i = 0; i < 4; i++) {
vacuum.d = (vacuum.d+3) % 4;
int nx = vacuum.x + dx[vacuum.d];
int ny = vacuum.y + dy[vacuum.d];
if(!inBound(nx, ny) || room[nx][ny] != 0) continue;
vacuum.x = nx;
vacuum.y = ny;
needToClean = true;
break;
}
// 2번 작업
if(!needToClean) {
int backDir = (vacuum.d+2) % 4;
int nx = vacuum.x + dx[backDir];
int ny = vacuum.y + dy[backDir];
// 2-2번 작업
if(!inBound(nx, ny) || room[nx][ny] == 1) break;
else{
vacuum.x = nx;
vacuum.y = ny;
}
}
}
}
static boolean inBound(int x, int y){
return !(x < 0 || y < 0 || x >= n || y >= m);
}
static void print(){
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(room[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
연합을 알기 위해서는 결국 bfs를 통해 조건을 만족하며 인접한 국가들을 모두 찾아야 한다. 대략적인 풀이 순서는 다음과 같다.
1. 아직 연합에 소속되지 않은 국가를 찾는다
2. 인접한 국가에 대해서 국경을 열 수 있는지 조건을 확인한다
3. bfs로 서로 인접한 모든 국가들을 연합에 소속시킨다
4. 해당 연합의 인구 이동을 반영한다
5. 위 과정을 더 이상 인구 이동이 없을 때까지 반복한다
1) 먼저 이차원 visited 배열을 통해 해당 국가가 이미 연합에 속해있는지를 확인하여 불필요하게 반복적인 연산을 피할 필요가 있다. 이때 boolean으로 설정해도 되지만, 나는 이후에 인구 이동을 편하게 계산하기 위해 int로 설정하여 연합의 번호를 저장하도록 했다. 따라서 어떤 연합에도 속하지 않을 경우 0값을 가지게 된다. 이 visited 배열은 새로운 날마다 초기화된다.
2, 3) 연합에 속하지 않은 국가를 찾았다면, bfs로 인구수를 비교하며 동일한 연합의 국가들을 찾는다. 인접은 상하좌우 4방향을 찾아야 한다. 만약 인접 인덱스가 전체 배열의 범위를 벗어나거나, 이미 어떤 연합에 속해있을 경우에는 넘어간다. 연합 국가를 찾을 때마다 그 인구수와 개수를 누적한다. 그렇게 연합 번호, 누적 인구수, 전체 국가수를 가진 Union이라는 객체를 만든다.
4) 위에서 구한 Union 객체를 통해 인구를 이동시킨다. visited 배열에 저장된 값과 연합 번호가 같은 국가들에 한해서 인구 값을 갱신한다.
5) 만약 Union 객체의 국가 수가 1이라면 연합이 이루어지지 않아 인구 이동이 발생하지 않았다는 것을 의미한다. 따라서 알고리즘 계산을 종료한다.
사실 처음에는 위에서 말한 boolean 방법으로 연합 소속 여부만 확인하고, 별도로 큐에 저장해 그에 속하는 국가들에만 접근하여 인구를 갱신하는 코드를 짰었다. 하지만 실행 시간에 차이가 나지 않았기 때문에 위 방법이 가독성 측면에서는 더 좋다고 생각하여 이렇게 포스팅을 하게 되었다.
코드
package week9;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ16234 {
static class Pos{
int x, y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
static class Union{
int unionNum, populationSum, countryCnt;
public Union(int unionNum, int populationSum, int countryCnt) {
this.unionNum = unionNum;
this.populationSum = populationSum;
this.countryCnt = countryCnt;
}
}
static int[][] countryMap, visited;
static int n, l, r;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
// 입력값 저장
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
countryMap = new int[n][n];
visited = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++)
countryMap[i][j] = Integer.parseInt(st.nextToken());
}
// 인구 이동
int dayCnt = 0;
while (checkBorder()) {
visited = new int[n][n];
dayCnt++;
}
System.out.println(dayCnt);
}
private static boolean checkBorder() {
// 변수 초기화
boolean isUnion = false;
int unionNum = 1;
// 인근 나라 인구 확인
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if(visited[x][y] != 0) continue;
// 연합끼리 국경 열기
Union union = openBorder(x, y, unionNum++);
// 두 개 이상의 국가가 연합이 되었다면 인구이동
if(union.countryCnt > 1){
isUnion = true;
movePopulation(union);
}
}
}
return isUnion;
}
private static void movePopulation(Union union) {
int newPopulation = union.populationSum / union.countryCnt;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(visited[i][j] != union.unionNum) continue;
countryMap[i][j] = newPopulation;
}
}
}
private static Union openBorder(int x, int y, int unionNum) {
// 변수 초기화
Queue<Pos> q = new LinkedList<>();
int populationSum = 0;
int countryCnt = 0;
// 인접한 국가를 bfs로 탐색
q.add(new Pos(x, y));
while(!q.isEmpty()) {
Pos cur = q.poll();
if(visited[cur.x][cur.y] != 0) continue;
visited[cur.x][cur.y] = unionNum;
populationSum += countryMap[cur.x][cur.y];
countryCnt++;
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
if (!inBound(nx, ny) || visited[nx][ny] != 0) continue;
int populationSub = Math.abs(countryMap[cur.x][cur.y] - countryMap[nx][ny]);
if (populationSub >= l && populationSub <= r)
q.add(new Pos(nx, ny));
}
}
return new Union(unionNum, populationSum, countryCnt);
}
private static boolean inBound(int x, int y) {
return !(x < 0 || y < 0 || x >= n || y >= n);
}
}
나는 입력 부분과 알고리즘 처리 구분을 구분하기 위해 추천 후보를 따로 배열에 저장했다. 그리고 추천 시 해당 후보를 바로바로 찾기 위해 map을 사용했고 만약 어떤 후보를 지워야 한다면 그냥 map에서 remove해주었다.
어떤 후보를 지워야하는 경우에는 (1)사진틀이 꽉 차있고 (2)이번에 추천받은 후보가 사진틀에 없다는 조건을 만족해야 한다. 사진틀의 최대 개수는 20개이기 때문에 전부 탐색해주었다. n개를 비교하며 추천횟수가 더 적거나, 만약 같다면 더 오래된 후보를 지우도록 한다. 최종 후보 결과를 출력할 때는 배열에 넣고 정렬해도 되겠지만, 나는 우선순위 큐를 사용하여 저장하는 동시에 값이 정렬되도록 했다.
코드
package week9;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ1713 {
static class Candidate {
int num; // 후보 번호
int recommendCnt; // 추천 횟수
int registerTime; // 사진이 등록된 시점
Candidate(int num, int registerTime){
this.num = num;
this.registerTime = registerTime;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력값 저장
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[] recommendArr = new int[m];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++)
recommendArr[i] = Integer.parseInt(st.nextToken());
// 추천 순서대로 작업
Map<Integer, Candidate> candidateMap = new HashMap<>();
for (int i = 0; i < m; i++) {
int key = recommendArr[i];
// 비어있는 사진틀이 있는지 확인
if(candidateMap.size() == n && candidateMap.get(key) == null){
Candidate eraseCandidate = null;
for(Candidate cur : candidateMap.values()){
if(eraseCandidate == null) eraseCandidate = cur;
// 추천 횟수가 적은 후보를 지움
else if(eraseCandidate.recommendCnt > cur.recommendCnt)
eraseCandidate = cur;
// 추천 횟수가 같으면 더 오래된 사진을 지움
else if(eraseCandidate.recommendCnt == cur.recommendCnt &&
eraseCandidate.registerTime > cur.registerTime)
eraseCandidate = cur;
}
candidateMap.remove(eraseCandidate.num);
}
// 추천받은 학생의 사진을 게시
Candidate candidate = candidateMap.getOrDefault(key, new Candidate(key, i));
candidate.recommendCnt++;
candidateMap.put(key, candidate);
}
// 최종 후보의 학생 번호를 출력
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(Candidate cur : candidateMap.values())
pq.add(cur.num);
while(!pq.isEmpty())
System.out.print(pq.poll() + " ");
}
}
