이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Silver I에 해당하는 문제들인 7576번 : 토마토, 1697번 : 숨바꼭질, 1932번 : 정수 삼각형을 풀이해보도록 하겠습니다.
7576번 : 토마토
상하좌우 네 방향에 인접해있는 토마토들이 영향을 받아 다음 날 같이 익는다고 할 때, 창고에 보관된 토마토들이 총 며칠이 지났을 때 모두 익게 되는지를 구하는 문제입니다.
문제가 길어서 예시 입력이 나오지는 않았지만 익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 들어있지 않은 칸은 -1로 입력되게 됩니다.
인접한 토마토들의 연결 관계에 대해 조사해야 하는 문제이므로 그래프 탐색(BFS, DFS) 문제임을 알 수 있습니다.
#include<stdio.h>
struct node { int x, y; } queue[1000005];
int tomato[1005][1005] = {0, }, day[1005][1005] = {0, }, var[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};
int M, N, count = 0, front = 0, rear = 1;
int BFS() {
int popX, popY;
while(++front < rear) {
for(int i=0; i<4; i++) {
popX = queue[front].x + var[0][i];
popY = queue[front].y + var[1][i];
if(popX >= 1 && popX <= M && popY >= 1 && popY <= N && tomato[popY][popX] == 0) {
tomato[popY][popX] = 1;
day[popY][popX] = day[queue[front].y][queue[front].x] + 1;
queue[rear].x = popX;
queue[rear++].y = popY;
count--;
}
}
}
if(!count) return day[queue[rear-1].y][queue[rear-1].x];
else return -1;
}
int main() {
scanf("%d %d", &M, &N);
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++) {
scanf("%d", &tomato[i][j]);
if(tomato[i][j] == 0) count++;
else if(tomato[i][j] == 1) {
queue[rear].x = j;
queue[rear++].y = i;
}
}
printf("%d", BFS());
}
토마토가 모두 익을 때까지 걸리는 최단 거리(기간)를 출력하는 문제이므로, DFS보다는 BFS로 해결해야 합니다.
따라서 큐를 이용하여 익지 않은 인접한 토마토가 탐색될 때마다 큐에 대입해줍니다.
상하좌우 검사 코드를 따로 작성하지 않고 var 배열을 이용하여 같은 코드가 4번 반복되는 것을 간략화시켰습니다.
day 배열은 visit과 비슷하게 구현하여 인접한 day 값으로부터 1을 더해주는 방식으로 기록하면 쉽게 해결 가능합니다.
1697번 : 숨바꼭질
입력받은 정수 N에서 1을 더하거나 빼고, 2배를 하는 몇 번의 과정을 거쳐 K로 가기 위한 최소의 연산이 몇 번 필요한지를 구하는 문제입니다.
N과 K의 범위가 10만 이하의 정수로 적지 않은 범위이기 때문에, DP와 BFS를 응용하여 해결해보도록 하겠습니다.
#include<stdio.h>
int N, K, num[100005] = {0, }, queue[100005] = {0, };
int BFS(int pos) {
int front = 0, rear = 1, pop;
queue[front] = pos;
while(front < rear) {
pop = queue[front++];
if(pop+1<=100000 && !num[pop+1] && pos!=pop+1) {
num[pop+1] = num[pop]+1;
queue[rear++] = pop+1;
if(pop+1 == K) break;
}
if(pop-1>=0 && !num[pop-1] && pos!=pop-1) {
num[pop-1] = num[pop]+1;
queue[rear++] = pop-1;
if(pop-1 == K) break;
}
if(pop*2<=100000 && !num[pop*2] && pos!=pop*2) {
num[pop*2] = num[pop]+1;
queue[rear++] = pop*2;
if(pop*2 == K) break;
}
}
return num[K];
}
int main() {
scanf("%d %d", &N, &K);
printf("%d", BFS(N));
}
N을 기준으로 +1, -1, ×2를 하여 나오는 수를 queue 배열에 저장한 뒤, 하나씩 pop하며 같은 연산을 반복하는 BFS 방식으로 문제를 해결하였습니다.
이 때 num 배열에는 N으로부터 해당 수까지 이동하는 데 걸리는 최소 이동 수를 저장하였습니다.
그렇게 되면 num[pop_new] = num[pop] + 1이라는 관계식이 성립하기 때문에 BFS 방식으로 탐색하면서 num 배열의 수들을 채울 수 있습니다.
num을 모든 범위에 채우는 방식보다는 pop에 K가 나오면 즉시 출력하고 프로그램이 종료되도록 작성하였습니다.
1932번 : 정수 삼각형
정수 삼각형이 입력되면 맨 위에서부터 아랫줄로 내려가며 수를 하나씩 택해 나올 수 있는 최댓값을 구하는 문제입니다.
줄이 늘어날수록 기하급수적으로 경우의 수가 많아지므로 DP를 사용해서 해결해야 합니다.
#include<stdio.h>
int triangle[505][505] = {0, }, maxSum[505][505] = {0, }, maxVal = 0;
int max(int a, int b) { return a>b?a:b; }
int main() {
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++) {
scanf("%d", &triangle[i][j]);
maxSum[i][j] = max(maxSum[i-1][j-1], maxSum[i-1][j]) + triangle[i][j];
if(maxSum[i][j] > maxVal) maxVal = maxSum[i][j];
}
printf("%d", maxVal);
}
같은 의미의 변수가 많아서 변수명을 짓기가 조금 힘들었습니다.
먼저 triangle 배열에 정수 삼각형을 입력받는 동시에, maxSum이라는 배열을 만들어서 i번째 줄 j번째 항까지 도달하는데 걸리는 최대 합을 구해서 바로 저장하도록 하였습니다.
동시에 maxVal이라는 최종적으로 출력할 변수를 선언하여 비교하고 마지막에 바로 print 해줄 수 있도록 작성하였습니다.