알고리즘
백준 16235 JAVA
infobox503
2024. 7. 10. 13:55
문제 유형
- 시뮬레이션
문제 접근
- 답
- 살아있는 나무 개수
- 주어지는 정보
- 땅 크기 N*N = 100
- 1년 마다의 연산 회수
- 봄
- 나무 100개 + 정렬(NlogN) = 120
- 여름
- 죽은 나무 100개 = 100
- 가을
- 나무 100개 * 인접 8칸 = 800
- 겨울
- 양분 추가 100 = 100
- 총합
- 1120 예상
- 봄
- 최대 기간 년도 K = 1000
- 총합
- 1000 * 1120 ⇒ 1,120,000
- ⇒ 완전 탐색 가능
- ⇒ 시뮬레이션 가능
import java.util.*;
import java.io.*;
class Tree implements Comparable<Tree>{
public int y,x,age;
Tree(int y, int x, int age)
{
this.y = y;
this.x = x;
this.age = age;
}
}
public class Main {
public static int N,M,K;
public static int[][] A;
public static int[][] map;
public static Deque<Tree> list = new LinkedList<>();
public static Queue<Tree>DeadTree = new LinkedList<>();
public static int[][] move = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
public static void spring()
{
int listSize = list.size();
for(int i = 0; i<listSize; i++)
{
Tree tree = list.pollFirst();
if(map[tree.y][tree.x] >= tree.age)
{
map[tree.y][tree.x] -= tree.age;
tree.age++;
list.addLast(tree);
}
else
{
DeadTree.add(tree);
}
}
}
public static void summer()
{
while(!DeadTree.isEmpty())
{
Tree tree = DeadTree.peek();
DeadTree.remove();
map[tree.y][tree.x] += (tree.age/2);
}
}
public static void fall()
{
List<Tree> addList = new ArrayList<>();
int listSize = list.size();
for(int i = 0; i<listSize; i++)
{
Tree tree = list.pollFirst();
list.addLast(tree);
if(tree.age % 5 == 0)
{
for(int j = 0; j<8; j++)
{
int moveY = tree.y + move[j][0];
int moveX = tree.x + move[j][1];
if(moveY < 0 || moveY >= N || moveX < 0 || moveX >= N)
{
continue;
}
addList.add(new Tree(moveY,moveX,1));
}
}
}
for(int i = 0; i<addList.size(); i++)
{
list.addFirst(addList.get(i));
}
}
public static void winter()
{
for(int i = 0; i<N; i++)
{
for(int j = 0; j<N; j++)
{
map[i][j] += A[i][j];
}
}
}
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());
K = Integer.parseInt(st.nextToken());
A = new int[N][N];
map = new int[N][N];
for(int i = 0; i<N; i++)
{
st = new StringTokenizer(br.readLine());
for(int j = 0; j<N; j++)
{
A[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i = 0; i<N; i++)
{
for(int j = 0; j<N; j++)
{
map[i][j] = 5;
}
}
for(int i = 0; i<M; i++)
{
st = new StringTokenizer(br.readLine());
int x,y,age;
y = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
age = Integer.parseInt(st.nextToken());
list.addLast(new Tree(y-1,x-1,age));
}
for(int i = 0; i<K; i++)
{
spring();
summer();
fall();
winter();
}
System.out.println(list.size());
}
}
실패 코드
- 문제점
- 자료구조가 적합하지 않음
- List<Tree> list = new ArrayList<>();
- 코드에서 삽입, 삭제가 빈번히 일어났음
- 연결리스트 기반이 아니라서 추가적인 연산이 들어간듯 함
- List<Tree> list = new ArrayList<>();
- QnA) ArrayList가 아닌, LinkedList를 쓰면 되지 않나?
- List<Tree> list = new LinkedList<>();
- 위 자료구조 또한 적합하지 않다.
- 조회 또한 빈번히 일어나므로, 적합X
- 자료구조가 적합하지 않음
import java.util.*;
import java.io.*;
class Tree implements Comparable<Tree>{
public int y,x,age;
Tree(int y, int x, int age)
{
this.y = y;
this.x = x;
this.age = age;
}
@Override
public int compareTo(Tree tree)
{
if(tree.age < age)
{
return 1;
}
else if(tree.age > age)
{
return -1;
}
return 0;
}
@Override
public String toString()
{
return this.y + ", " + this.x +", " + this.age;
}
}
public class Main {
public static int N,M,K;
public static int[][] A;
public static int[][] map;
public static List<Tree> list = new ArrayList<>();
public static List<Tree>DeadTree = new ArrayList<>();
public static int[][] move = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
public static void Print()
{
Collections.sort(list);
for(Tree tree : list)
{
System.out.println(tree);
}
}
public static void spring()
{
Collections.sort(list);
int listSize = list.size();
for(int i = 0; i<listSize; i++)
{
Tree tree = list.get(i);
if(map[tree.y][tree.x] >= tree.age)
{
map[tree.y][tree.x] -= tree.age;
list.get(i).age++;
}
else
{
DeadTree.add(tree);
}
}
for(int i = 0; i<DeadTree.size(); i++)
{
list.remove(DeadTree.get(i));
}
}
public static void summer()
{
int DeadTreeSize = DeadTree.size();
for(int i = 0; i<DeadTreeSize; i++)
{
Tree tree = DeadTree.get(i);
map[tree.y][tree.x] += (tree.age / 2);
}
while(!DeadTree.isEmpty())
{
DeadTree.remove(0);
}
}
public static void fall()
{
List<Tree> addList = new ArrayList<>();
int listSize = list.size();
for(int i = 0; i<listSize; i++)
{
Tree tree = list.get(i);
if(tree.age % 5 == 0)
{
for(int j = 0; j<8; j++)
{
int moveY = tree.y + move[j][0];
int moveX = tree.x + move[j][1];
if(moveY < 0 || moveY >= N || moveX < 0 || moveX >= N)
{
continue;
}
addList.add(new Tree(moveY,moveX,1));
}
}
}
for(int i = 0; i<addList.size(); i++)
{
list.add(addList.get(i));
}
}
public static void winter()
{
for(int i = 0; i<N; i++)
{
for(int j = 0; j<N; j++)
{
map[i][j] += A[i][j];
}
}
}
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());
K = Integer.parseInt(st.nextToken());
A = new int[N][N];
map = new int[N][N];
for(int i = 0; i<N; i++)
{
st = new StringTokenizer(br.readLine());
for(int j = 0; j<N; j++)
{
A[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i = 0; i<N; i++)
{
for(int j = 0; j<N; j++)
{
map[i][j] = 5;
}
}
for(int i = 0; i<M; i++)
{
st = new StringTokenizer(br.readLine());
int x,y,age;
y = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
age = Integer.parseInt(st.nextToken());
list.add(new Tree(y-1,x-1,age));
}
// Print();
// System.out.println("------");
for(int i = 0; i<K; i++)
{
spring();
summer();
fall();
winter();
// Print();
// System.out.println("------");
}
System.out.println(list.size());
}
}