[프로그래머스 / C언어] 지게차와 크레인 BFS로 풀기
프로그래머스 코딩테스트 문제 중, 지게차와 크레인 문제를 BFS를 활용해서 풀어보았다.
https://school.programmers.co.kr/learn/courses/30/lessons/388353
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
BFS와 구현에 대한 설명은, 아래 내 블로그 글을 통해 확인할 수 있다.
https://programming-diary-ina.tistory.com/30
[백준 1260번/C언어] DFS와 BFS, Queue로 풀이
백준 1260번 문제를 큐(Queue)로 풀어보았습니다. 백준 1260번: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점
programming-diary-ina.tistory.com
코드가 길고 문제가 복잡하므로, 파트를 나누어서 언급하려고 한다. 순서는 아래와 같다.
1. solution function으로 보는 전체 흐름
2. 초기 설정 (access 배열 설정)
3. 크레인 작업
4. 지게차 작업
1. solution function으로 보는 전체 흐름
이 코드에서는 solution이 제출해야 하는 메인 함수이다. 따라서 solution함수를 보면서 문제의 전체 흐름을 보겠다. access 배열의 경우 storage 배열이 const 배열이기 때문에, 같은 위치의 컨테이너가 접근가능한지, 이미 꺼내졌는지 등의 정보를 저장하는 배열의 역할을 한다. 이 배열을 가지고 requests 배열을 순회하며, request[i]의 길이가 2일 경우 크레인 작업을 수행시키고, 1일 경우 지게차 작업을 수행시킨다. 이때 크레인과 지게차 작업을 하는 함수의 리턴값은 꺼내진 컨테이너의 개수이므로, 전체 개수를 저장해 둔 answer 변수에서 리턴값만큼을 빼준다.
int solution(const char* storage[], size_t storage_len, const char* requests[], size_t requests_len){
int wid = strlen(storage[0]);
int** access = get_access(storage, storage_len, wid);
int answer = storage_len * wid;
for (int i = 0; i < requests_len; i++) {
char target = requests[i][0];
if (strlen(requests[i]) == 2) {
answer -= crane_work(target, storage, storage_len, wid, &access);
} else {
answer -= lift_work(target, storage, storage_len, wid, &access);
}
}
for (int i = 0; i < storage_len; i++) free(access[i]);
free(access);
return answer;
}
2. 초기 설정 (access 배열 설정)
앞서 언급했듯, storage 배열이 const로 주어졌기 때문에, 상태를 표기해둘 같은 크기의 access 배열을 만들어야 한다. 이를 get_access 함수로 수행했다. 상태를 표기하기 위한 enum도 선언해 줬는데, 그 의미는 아래와 같다.
ACCESSIBLE : 지게차로 접근 가능한 (창고 외부와 연결된) 컨테이너 상태
UNACCESSIBLE : 지게차로는 접근이 불가능하고 크레인으로만 접근 가능한 컨테이너 상태
NONE : 이미 꺼내진 컨테이너
PROCESS_NONE : 지게차 작업 중 꺼내진 컨테이너
PROCESS_ACCESS : 지게차 작업 중 접근 가능해진 컨테이너
PROCESS_ 상태를 추가한 이유는, 지게차 작업을 하면서 꺼내진 컨테이너로 인해 접근이 가능해진 컨테이너가 그 작업 동안에는 접근 가능하다고 분류되어서는 안되는데, 바로 ACCESSIBLE이나 NONE으로 상태를 바꿔주면, 그 작업 동안에 접근 가능하다고 분류되어 같이 꺼내지는 경우가 발생할 수 있기 때문이다. 예를 들어, 아래 사진과 같은 경우에, A가 하나만 꺼내져야 하는데, 바로 옆에 다른 A도 함께 꺼내지는 경우를 방지하기 위해서 PROCESS_ 상태가 필요한 것이다. 지게차 작업이 끝나고 나면, PROCESS_NONE은 NONE으로, PROCESS_ACCESS는 ACCESS로 바꿔준다.
이를 바탕으로 초기 access 배열은 테두리만 ACCESSIBLE로, 나머지는 UNACCESSIBLE로 설정해준다.
enum {
ACCESSIBLE,
UNACCESSIBLE,
NONE,
PROCESS_NONE,
PROCESS_ACCESS
};
int** get_access(const char* storage[], size_t storage_len, int wid) {
int** access = (int**)malloc(sizeof(int*) * storage_len);
for (int i = 0; i < storage_len; i++) {
access[i] = (int*)malloc(sizeof(int) * wid);
for (int j = 0; j < wid; j++) {
if (i == 0 || j == 0 || i == storage_len-1 || j == wid-1) {
access[i][j] = ACCESSIBLE;
} else access[i][j] = UNACCESSIBLE;
}
}
return access;
}
3. 크레인 작업
크레인 작업은 비교적 간단한다. storage를 순회하며, requests에서 알려준 타깃이 되는 알파벳과 같은 알파벳을 가진 남아있는 모든 컨테이너를 꺼내면 되기 때문이다. 꺼내진 컨테이너는 NONE으로 상태를 변경해 준다.
int crane_work(char target, const char* storage[], int x_len, int y_len, int*** access) {
int count = 0;
for (int x = 0; x < x_len; x++) {
for (int y = 0; y < y_len; y++) {
if (storage[x][y] == target && (*access)[x][y] != NONE) {
count++;
(*access)[x][y] = NONE;
}
}
}
return count;
}
4. 지게차 작업
사실 이 문제의 관건은 이 부분이다. 그래서 코드도 가장 길고, 가장 애먹었던 작업이기도 하다. 처음에는 재귀함수로 문제를 해결하려 했는데, 메모리 관리나 여러 측면에서 단점이 있어서 loop와 queue를 활용한 BFS로 방식을 바꿨다.
우선 lift_work() 함수에서 전체 storage를 순회하면서 우리가 꺼내고자 하는 target 컨테이너를 찾는다. 만약 찾았다면, is_accessible 함수를 통해 해당 함수가 지게차로 접근 가능한 상태인지를 확인하고, 그렇다면 그 컨테이너의 상태를 NONE으로 그리고 좌우상하의 컨테이너들의 상태를 ACCESSIBLE로 바꿔준다. (ACCESSIBLE한 컨테이너가 사라지면 그 주변 컨테이너들은 자동으로 외부와 연결된다.)
is_accessible 함수는 앞서 언급했듯, loop와 queue를 활용한 BFS를 사용했다. 조건을 충족하는(상태가 NONE이고, 아직 방문하지 않은) 컨테이너 위치를 queue에 저장해 놓고, 해당 컨테이너가 외부와 연결되어 있는지를 확인해 나가는 방식이다. 우리가 확인하려는 컨테이너 상하좌우가 비어있어도, 그 빈 공간이 외부와 연결되어 있는지는 알 수 없기 때문에 이렇게 확인해야 한다. 따라서 queue에 요소가 남아있는 동안에, 반복적으로 queue의 head 컨테이너의 상하좌우가 조건에 맞는지 확인하여 queue에 넣는 작업을 반복한다. 반복 작업 중에 외부와 연결되어 있는 요소를 발견하는 즉시 true를 리턴하면 된다. 반복 작업 중 true가 리턴되지 않으면, 우리가 확인 중인 컨테이너가 외부와 연결되어 있지 않다는 의미이므로 false를 리턴해주면 된다.
int* set_queue(int x, int y) {
int* q = (int*)malloc(sizeof(int) * 2);
q[0] = x;
q[1] = y;
return q;
}
bool is_accessible(int x, int y, int*** access, int x_len, int y_len) {
if ((*access)[x][y] == NONE) return false;
if ((*access)[x][y] == ACCESSIBLE) return true;
int** queue = (int**)malloc(sizeof(int*) * x_len * y_len);
int head = 0, tail = 0;
bool** visited = (bool**)malloc(sizeof(bool*) * x_len);
for (int i = 0; i < x_len; i++) {
visited[i] = (bool*)calloc(y_len, sizeof(bool));
}
queue[tail++] = set_queue(x, y);
// BFS 하면서 queue 내에 하나라도 끝에 도달하는 거 있으면 true
while (head < tail) {
int cur_x = queue[head][0], cur_y = queue[head][1];
free(queue[head++]);
if (visited[cur_x][cur_y]) continue;
if (cur_x == 0 || cur_y == 0 || cur_x == x_len-1 || cur_y == y_len-1) {
if ((*access)[cur_x][cur_y] == NONE) {
for (int i = head; i < tail; i++) free(queue[i]);
free(queue);
for (int i = 0; i < x_len; i++) free(visited[i]);
free(visited);
return true;
}
}
if ((*access)[cur_x+1][cur_y] == NONE && visited[cur_x+1][cur_y] == false)
queue[tail++] = set_queue(cur_x+1, cur_y);
if ((*access)[cur_x-1][cur_y] == NONE && visited[cur_x-1][cur_y] == false)
queue[tail++] = set_queue(cur_x-1, cur_y);
if ((*access)[cur_x][cur_y+1] == NONE && visited[cur_x][cur_y+1] == false)
queue[tail++] = set_queue(cur_x, cur_y+1);
if ((*access)[cur_x][cur_y-1] == NONE && visited[cur_x][cur_y-1] == false)
queue[tail++] = set_queue(cur_x, cur_y-1);
visited[cur_x][cur_y] = true;
}
free(queue);
for (int i = 0; i < x_len; i++) free(visited[i]);
free(visited);
return false;
}
int lift_work(char target, const char* storage[], int x_len, int y_len, int*** access) {
int count = 0;
for (int x = 0; x < x_len; x++) {
for (int y = 0; y < y_len; y++) {
if (storage[x][y] == target && is_accessible(x, y, access, x_len, y_len)) {
count++;
(*access)[x][y] = PROCESS_NONE;
if (x > 0 && (*access)[x-1][y] == UNACCESSIBLE) (*access)[x-1][y] = PROCESS_ACCESS;
else if (x < (x_len-1) && (*access)[x+1][y] == UNACCESSIBLE)
(*access)[x+1][y] = PROCESS_ACCESS;
if (y > 0 && (*access)[x][y-1] == UNACCESSIBLE) (*access)[x][y-1] = PROCESS_ACCESS;
else if (y < (y_len-1) && (*access)[x][y+1] == UNACCESSIBLE)
(*access)[x][y+1] = PROCESS_ACCESS;
}
}
}
if (count == 0) return count;
for (int x = 0; x < x_len; x++) {
for (int y = 0; y < y_len; y++) {
if ((*access)[x][y] == PROCESS_NONE) {
(*access)[x][y] = NONE;
} else if ((*access)[x][y] == PROCESS_ACCESS) {
(*access)[x][y] = ACCESSIBLE;
}
}
}
return count;
}
마지막으로 전체 코드는 아래와 같다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
enum {
ACCESSIBLE,
UNACCESSIBLE,
NONE,
PROCESS_NONE,
PROCESS_ACCESS
};
int** get_access(const char* storage[], size_t storage_len, int wid) {
int** access = (int**)malloc(sizeof(int*) * storage_len);
for (int i = 0; i < storage_len; i++) {
access[i] = (int*)malloc(sizeof(int) * wid);
for (int j = 0; j < wid; j++) {
if (i == 0 || j == 0 || i == storage_len-1 || j == wid-1) {
access[i][j] = ACCESSIBLE;
} else access[i][j] = UNACCESSIBLE;
}
}
return access;
}
int crane_work(char target, const char* storage[], int x_len, int y_len, int*** access) {
int count = 0;
for (int x = 0; x < x_len; x++) {
for (int y = 0; y < y_len; y++) {
if (storage[x][y] == target && (*access)[x][y] != NONE) {
count++;
(*access)[x][y] = NONE;
}
}
}
return count;
}
int* set_queue(int x, int y) {
int* q = (int*)malloc(sizeof(int) * 2);
q[0] = x;
q[1] = y;
return q;
}
bool is_accessible(int x, int y, int*** access, int x_len, int y_len) {
if ((*access)[x][y] == NONE) return false;
if ((*access)[x][y] == ACCESSIBLE) return true;
int** queue = (int**)malloc(sizeof(int*) * x_len * y_len);
int head = 0, tail = 0;
bool** visited = (bool**)malloc(sizeof(bool*) * x_len);
for (int i = 0; i < x_len; i++) {
visited[i] = (bool*)calloc(y_len, sizeof(bool));
}
queue[tail++] = set_queue(x, y);
// BFS 하면서 queue 내에 하나라도 끝에 도달하는 거 있으면 true
while (head < tail) {
int cur_x = queue[head][0], cur_y = queue[head][1];
free(queue[head++]);
if (visited[cur_x][cur_y]) continue;
if (cur_x == 0 || cur_y == 0 || cur_x == x_len-1 || cur_y == y_len-1) {
if ((*access)[cur_x][cur_y] == NONE) {
for (int i = head; i < tail; i++) free(queue[i]);
free(queue);
for (int i = 0; i < x_len; i++) free(visited[i]);
free(visited);
return true;
}
}
if ((*access)[cur_x+1][cur_y] == NONE && visited[cur_x+1][cur_y] == false)
queue[tail++] = set_queue(cur_x+1, cur_y);
if ((*access)[cur_x-1][cur_y] == NONE && visited[cur_x-1][cur_y] == false)
queue[tail++] = set_queue(cur_x-1, cur_y);
if ((*access)[cur_x][cur_y+1] == NONE && visited[cur_x][cur_y+1] == false)
queue[tail++] = set_queue(cur_x, cur_y+1);
if ((*access)[cur_x][cur_y-1] == NONE && visited[cur_x][cur_y-1] == false)
queue[tail++] = set_queue(cur_x, cur_y-1);
visited[cur_x][cur_y] = true;
}
free(queue);
for (int i = 0; i < x_len; i++) free(visited[i]);
free(visited);
return false;
}
int lift_work(char target, const char* storage[], int x_len, int y_len, int*** access) {
int count = 0;
for (int x = 0; x < x_len; x++) {
for (int y = 0; y < y_len; y++) {
if (storage[x][y] == target && is_accessible(x, y, access, x_len, y_len)) {
count++;
(*access)[x][y] = PROCESS_NONE;
if (x > 0 && (*access)[x-1][y] == UNACCESSIBLE) (*access)[x-1][y] = PROCESS_ACCESS;
else if (x < (x_len-1) && (*access)[x+1][y] == UNACCESSIBLE)
(*access)[x+1][y] = PROCESS_ACCESS;
if (y > 0 && (*access)[x][y-1] == UNACCESSIBLE) (*access)[x][y-1] = PROCESS_ACCESS;
else if (y < (y_len-1) && (*access)[x][y+1] == UNACCESSIBLE)
(*access)[x][y+1] = PROCESS_ACCESS;
}
}
}
if (count == 0) return count;
for (int x = 0; x < x_len; x++) {
for (int y = 0; y < y_len; y++) {
if ((*access)[x][y] == PROCESS_NONE) {
(*access)[x][y] = NONE;
} else if ((*access)[x][y] == PROCESS_ACCESS) {
(*access)[x][y] = ACCESSIBLE;
}
}
}
return count;
}
int solution(const char* storage[], size_t storage_len, const char* requests[], size_t requests_len){
int wid = strlen(storage[0]);
int** access = get_access(storage, storage_len, wid);
int answer = storage_len * wid;
for (int i = 0; i < requests_len; i++) {
char target = requests[i][0];
if (strlen(requests[i]) == 2) {
answer -= crane_work(target, storage, storage_len, wid, &access);
} else {
answer -= lift_work(target, storage, storage_len, wid, &access);
}
}
for (int i = 0; i < storage_len; i++) free(access[i]);
free(access);
return answer;
}