문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
줄기세포 배양 시뮬레이션 프로그램을 만들려고 한다.
줄기세포들을 배양 용기에 도포한 후 일정 시간 동안 배양을 시킨 후 줄기 세포의 개수가 몇 개가 되는지 계산하는 시뮬레이션 프로그램을 만들어야 한다.
하나의 줄기 세포는 가로, 세로 크기가 1인 정사각형 형태로 존재하며 배양 용기는 격자 그리드로 구성되어 있으며 하나의 그리드 셀은 줄기 세포의 크기와 동일한 가로, 세로 크기가 1인 정사각형이다.
각 줄기 세포는 생명력이라는 수치를 가지고 있다.
초기 상태에서 줄기 세포들은 비활성 상태이며 생명력 수치가 X인 줄기 세포의 경우 X시간 동안 비활성 상태이고 X시간이 지나는 순간 활성 상태가 된다.
줄기 세포가 활성 상태가 되면 X시간 동안 살아있을 수 있으며 X시간이 지나면 세포는 죽게 된다.
세포가 죽더라도 소멸되는 것은 아니고 죽은 상태로 해당 그리드 셀을 차지하게 된다.
활성화된 줄기 세포는 첫 1시간 동안 상, 하, 좌, 우 네 방향으로 동시에 번식을 한다.
번식된 줄기 세포는 비활성 상태이다.
하나의 그리드 셀에는 하나의 줄기 세포만 존재할 수 있기 때문에 번식하는 방향에 이미 줄기 세포가 존재하는 경우 해당 방향으로 추가적으로 번식하지 않는다.
두 개 이상의 줄기 세포가 하나의 그리드 셀에 동시 번식하려고 하는 경우 생명력 수치가 높은 줄기 세포가 해당 그리드 셀을 혼자서 차지하게 된다.
줄기 세포의 크기에 비해 배양 용기의 크기가 매우 크기 때문에 시뮬레이션에서 배양 용기의 크기는 무한하다고 가정한다.
아래 [그림1]과 [그림2]는 줄기 세포가 번식하는 예를 나타낸다.
[그림 1]
[그림 2]
줄기 세포의 초기 상태 정보와 배양 시간 K시간이 주어질 때, K시간 후 살아있는 줄기 세포(비활성 상태 + 활성 상태)의 총 개수를 구하는 프로그램을 작성하라.
[제약 사항]
- 초기 상태에서 줄기 세포가 분포된 영역의 넓이는 세로 크기 N, 가로 크기 M이며 N, M은 각각 1 이상 50 이하의 정수이다. (1≤N≤50, 1≤M≤50)
- 배양 시간은 K시간으로 주어지며 K는 1 이상 300 이하의 정수이다. (1≤K≤300)
- 배양 용기의 크기는 무한하다. 따라서 줄기 세포가 배양 용기 가장자리에 닿아서 번식할 수 없는 경우는 없다.
- 줄기 세포의 생명력 X는 1 이상 10 이하의 정수이다. (1≤X≤10)
[입력]
입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어진다.
그 다음 줄부터는 각 테스트 케이스가 주어지며
각 테스트 케이스의 첫째 줄에는 초기 상태에서줄기 세포가 분포된 세로 크기 N, 가로 크기 M, 배양 시간 K가 순서대로 주어진다.
다음 N 줄에는 각 줄마다 M개의 그리드 상태 정보가 주어진다.
1~10까지의 숫자는 해당 그리드 셀에 위치한 줄기 세포의 생명력을 의미하며,
0인 경우 줄기 세포가 존재하지 않는 그리드이다.
[출력]
테스트 케이스 T에 대한 결과는 “#T”을 찍고,
배양을 K시간 시킨 후 배양 용기에 있는 살아있는 줄기 세포(비활성 상태 + 활성 상태)의 개수를 출력한다. (T는 테스트케이스의 번호를 의미하며 1부터 시작한다. )
풀이
풀다가 집중력이 흐트러지면 그때부터 답이 없다.
디버깅 지옥에 빠지는 뭣같은 문제.
처음부터 탐색 조건 설계를 잘 잡고 드가야 한다.
하지만 엣지 케이스를 모두 그려보면서 처음부터 고려하기가 쉽지 않다.
디버깅해가면서 찾아내고, 맞왜틀, 왜안돼 등등 중얼거리다가 결국 맞았다.
우선 그래프 최대 크기부터 알아보자.
k가 300이고, 줄기 세포의 생명력을 1이라고 해보자.
줄기 세포의 생명력은 2초마다 한 칸씩 이동한다.
즉, 생명력이 1인 줄기세포가 0,0칸에 있다면 최대 -150까지 갈 수 있는 것이다.
만약 이 줄기세포가 50,50에 있다면 최대 200까지 갈 수 있다.
따라서 배열의 크기를 넉넉히 400 정도로 잡고, 인덱스의 시작 지점을 175 정도로 중간지점부터 시작하면 된다.
0,0칸에 있던 줄기세포는 175,175
50,50칸에 있던 줄기세포는 225,225가 되고,
적어도 이 문제에서 요구하는 '무한'한 크기의 배양 용기를 구현할 수 있다.
본인은 i,j 줄기 세포의 생명력을 graph[i][j] = life
i,j 줄기 세포 생명력의 변화를 visited[i][j] = life
죽은 상태를 life = INF(-999)로 표현하였다.
graph[i][j] 가 2이면, 매 시간마다 visited[i][j]가 1씩 마이너스 되고, visited 값에 따른 상태는 다음과 같다.
visited[i][j]==2 // 비활성화(초기)
visited[i][j]==1 // 비활성화
visited[i][j]==0 // 활성화
vsited[i][j]==-1 //활성화
visited[i][j]==-2 //die
이 상태를 가지고
//visited !=0 && graph !=0 비활성화 상태
//visited ==0 && graph !=0 활성화 상태
//visited ==-1 && graph !=0 번식
//visited <0 && visited == graph 죽은 상태
라는 식을 세울 수 있고, 분기 처리는 능력껏 하면 된다.
추가적으로 굳이 queue를 사용하지 않아도 되고, 두 줄기 세포가 하나의 칸에 동시에 번식하려고 하는 경우 때문에 조금 까다로웠으며, 이를 대응하기 위해 큐에 바로 삽입하지 않고, temp[][]에 넣어서 중복을 없앤 뒤 큐에 삽입해주었다.
코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Node{
public int r,c;
public Node(int r, int c) {
this.r = r;
this.c = c;
}
}
class Solution {
static int n,m,k;
static int[][] graph;
static int[][] visited;
static final int MAX =410;
static final int DEFAULT =150;
static final int INF = -999;
static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
static Queue<Node> q;
static int t;
static int answer=0;
//visited !=0 && graph !=0 비활성화 상태
//visited ==0 && graph !=0 활성화 상태
//visited ==-1 && graph !=0 번식
//visited == -x == graph 죽은 상태
static void bfs() {
int time=0;
while(!q.isEmpty()) {
if(time++==k) {
return;
}
int size = q.size();
//매 턴
int [][] temp = new int[MAX][MAX];
for(int i=0; i<size; i++) {
Node curNode = q.poll();
int cr = curNode.r;
int cc = curNode.c;
visited[cr][cc]--;
//번식
if(visited[cr][cc]==-1) {
for(int d =0; d<4; d++) {
int nr = cr + dir[d][0];
int nc = cc + dir[d][1];
//다음 칸에 이미 뭐가 있으면 스킵 or 덮ㄷ기
if(graph[nr][nc]>0) {
//만약 동시에 들어온 경우 비교
if(temp[nr][nc]>0 && graph[nr][nc] == visited[nr][nc]) {
if(graph[nr][nc]<graph[cr][cc]) {
graph[nr][nc] = graph[cr][cc];
visited[nr][nc] = graph[cr][cc];
temp[nr][nc]=graph[cr][cc];
}
}
}
else {
if(graph[nr][nc]==INF) continue;
if(graph[nr][nc]==0) {
graph[nr][nc] = graph[cr][cc];
visited[nr][nc] = graph[cr][cc];
temp[nr][nc]=graph[cr][cc];
}
}
}
}
//die
if(visited[cr][cc]== -graph[cr][cc]) {
graph[cr][cc] =INF;
}
temp[cr][cc]=graph[cr][cc];
}
q.clear();
answer=0;
for(int i=0; i<MAX;i++) {
for(int j=0; j<MAX;j++) {
if(temp[i][j]>0) {
answer++;
q.add(new Node(i,j));
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for(t=1; t<=T; t++) {
//input
graph = new int[MAX][MAX];
visited = new int[MAX][MAX];
q = new LinkedList<Node>();
StringTokenizer tk = new StringTokenizer(br.readLine());
n = Integer.parseInt(tk.nextToken());
m = Integer.parseInt(tk.nextToken());
k = Integer.parseInt(tk.nextToken());
for(int i=0; i<n; i++) {
tk = new StringTokenizer(br.readLine());
for(int j=0; j<m;j ++) {
int num = Integer.parseInt(tk.nextToken());
if(num>0)
q.add(new Node(DEFAULT+i, DEFAULT+j));
visited[DEFAULT+i][DEFAULT+j] = num;
graph[DEFAULT+i][DEFAULT+j] = num;
}
}
//solve
bfs();
//output
bw.write("#" + t+ " " + answer +'\n');
}
bw.close();
}
}'알고리즘 문제 풀이 > swea' 카테고리의 다른 글
| swea 2117 홈 방범 서비스 Java (완전탐색) (0) | 2022.03.06 |
|---|---|
| swea 7465 창용 마을 무리의 개수 Java (dfs, union-find) (0) | 2022.03.03 |
| swea 1953 탈주범 검거 Java (bfs) (0) | 2022.03.03 |
| swea 2115 벌꿀채취 Java (백트래킹) (0) | 2022.03.01 |
| swea 4012 요리사 Java (조합) (0) | 2022.02.28 |
댓글