[프로그래머스] LV3 : 2025 프로그래머스 코드챌린지 1차 예선 :: 지게차와 크레인
이번 문제풀이에서 배운 것들
std::string(size_t n, char c)
하나의 문자 c가 n번 반복되는 문자열을 생성하는 string의 생성자(constructor)
- 인자 : 반복하고 싶은 횟수 n, 반복하고 싶은 문자 c
- 반환값 : c를 n번 반복한 문자열(string)
🔻Programmers C++ Reference (정의 (2) 참고)
https://devdocs.programmers.co.kr/cpp/string/basic_string/basic_string
#include <string>
#include <iostream>
using namespace std;
// 'A'라는 문자를 10번 반복한 문자열 생성
std::string s(10, 'A');
std::cout << s << std::endl; // "AAAAAAAAAA"std::queue
선입선출(First In First Out) 방식의 STL
🔻Programmers C++ Reference
https://devdocs.programmers.co.kr/cpp/container/queue
#include <iostream>
#include <queue>
// Constructor
queue<pair<int, int>> qu;
// Operation : Push
qu.push({1, 1});
qu.push({1, 2});
qu.push({2, 1});
// Operation : Pop
qu.pop();
// Info : First element
cout << "qu.front(): " << qu.front() << "\n";
// Info : Last element
cout << "qu.back(): " << qu.back() << "\n";
// Info : Emptiness
cout << "!qu.empty(): " << !qu.empty() << "\n";
// Info : Size
cout << "qu.size(): " << qu.size() << "\n";문제 분석과 풀이 기록
Flood-Fill 응용 : 경계조건 명시 탐색 vs Padding
이 문제에서 지게차가 제거할 수 있는 컨테이너를 탐색하는데는 Flood-Fill과 유사한 기법이 사용됩니다.
Flood-Fill은 다차원 배열에서 특정 칸과 연결된 모든 칸들을 찾는 데 사용되는 기법인데요.
- 어떠한 칸을 기준으로
- 인접한 칸을 탐색하여 표시하는 작업을
- 인접한 칸을 더 이상 찾을 수 없을 때 까지
- 반복하는 형태로 구현합니다.
구현에는 트리 탐색 기법에서의 DFS(재귀함수)나 BFS(Queue 응용)이 주로 사용되는데, 이 부분은 나중에 알아보도록 하고
논리적인 관점에서 '시작점이 주어지는 공간 바깥에 있는 경우'에
Flood-Fill을 구현하는 두 가지 방법에 대해서 살펴보도록 하겠습니다..
방법 1 : 이번에 탐색하는 칸이 "경계조건" 인지 확인하는 방식의 풀이
이 방법은 사람이 문제를 푸는 방법과 유사합니다.
배열의 어떤 칸이 "테두리"인지 아닌지 확인해서, 테두리라면 "다른 절차"를 사용하는 것이죠.
이런 경우에는 큐를 활용한 BFS를 통해서 구현하는 게 좋습니다.
지게차를 통한 물건 인출 요청이 있을 때
- Boundary에 대해서 "BFS 시작 전 큐 삽입"
- Non Boundary에 대해서 "BFS 시작 후에만 큐 삽입"
을 수행하는 방식의 코드를 사용할 수 있고, 의사코드로 간단히 작어보자면 아래와 같을겁니다.
for BoundaryPoint in AllBoundaryPoints:
qu.Push(BoundaryPoint)
while not qu.Empty():
r, c = qu.Fromt()
if Storage(r, c) == RequestedTarget:
HitAction()
elif Storage(r, c) == 0:
for Point in notPushedPoints:
qu.Push(notPushedPoints)방법 2 : 테두리에 진입가능한 "패딩"을 추가하는 방법식의 풀이
이 방법은 알고리즘 친화적입니다.
배열의 어떤 칸이 "테두리"인지 확인하지 않고, 모든 칸에 대해서 "동일한 절차"를 사용하게 됩니다.
여담이지만, 저는 이 방식의 문제풀이를 더 선호합니다. 코드 구성이 깔끔하거든요.
이렇게 하면 전형적인 DFS로 풀어도 된다는 장점이 있습니다.
지게차를 통한 물건 인출 요청이 있을 때의 동작을 의사코드로 간단히 작어보자면 아래와 같을겁니다.
# Main Part of DFS Code logic
if Storage(r, c) == RequestedTarget:
HitAction()
return
elif Storage(r, c) == 0:
for Point in notVisitedPoints:
qu.Push(notVisitedPoints)트리 탐색 Trick : 하위 조건을 더 이상 탐색하기 싫으면 : 'Hit 후 return;'
저는 부트캠프 출신 개발자라서 트리 탐색에서 하위 조건을 더 이상 탐색하기 싫을때,
그러니까 "백트래킹"을 하고 싶을 때에는 continue 구문을 사용하는 스타일을 정형으로 배웠습니다.
왜 continue를 쓰는지는 깊게 생각해보지 않고 그저 따라하기 급급했는데,
이 문제를 풀면서 백트래킹을 수행하는 두 가지 방법의 차이점을 명확히 알 수 있게 된 것도 개인적으로는 큰 성과입니다.
| 백트래킹 구문 | 건너뛰려는 대상 | 이번 문제에서는 |
| continue; | 이번 단위동작을 시작한 "부모"에서 파생되는 "특정한 자식" Case | 표 경계를 벗어나는 자식 Case 이미 탐색예약이 되어있거나 탐색한 자식 Case |
| return; | 이번 단위동작을 시작한 "부모"에서 파생되는 "모든 자식" Case | 지게차에 의한 인출이 일어난 위치의 자식 Case |
위에서 BFS를 사용한 "경계조건" 검사에서는 이 'Hit 후 return' 전략은 'Hit 후 Queue에 넣지 않기' 전략이 됩니다.
모든 TC 통과한 코드
Padding을 사용한 코드
더보기
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<string> area;
vector<vector<int>> visited;
int answer = 0;
void printArea(void)
{
cout << "\n";
for(auto a : area)
{
cout << a << "\n";
}
}
// DFS 탐색
void jigecha(int depth, char target, int r, int c)
{
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
// [conditional] Initialize visited/popped_now array if first call of this function
// [AoU] first call is always jigecha(0, target, 0, 0)
if(depth == 0)
{
visited = vector<vector<int>>(area.size(), vector<int>(area[0].size(), 0));
}
// [DFS] Entry Action : Mark (r, c) as visited cell
visited[r][c] = 1;
// [Main Action] Check (r, c) holds 'target'
if(area[r][c] == target)
{
area[r][c] = '0';
answer--;
// KICK
return;
}
// [DFS] Call Next
for(int d=0; d<4; d++)
{
int nr = r + dr[d];
int nc = c + dc[d];
if(nr < 0 || nr >= area.size() || nc < 0 || nc >= area[0].size()) continue;
if(visited[nr][nc] == 1) continue;
if(area[r][c] != '0') continue;
jigecha(depth + 1, target, nr, nc);
}
return;
}
void crane(char target)
{
// [Sweep] Check All cells
for(int r=0; r<area.size(); r++)
{
for(int c=0; c<area[r].size();c++)
{
// [Main Action] Check (r, c) holds 'target'
if(area[r][c] == target)
{
area[r][c] = '0';
answer--;
}
}
}
return;
}
void procInput(vector<string> &storage)
{
answer = storage.size() * storage[0].size();
area = vector<string>();
area.push_back(string(storage[0].size() + 2 , '0'));
for(auto &str : storage) area.push_back('0' + str + '0');
area.push_back(string(storage[0].size() + 2 , '0'));
return;
}
int solution(vector<string> storage, vector<string> requests) {
procInput(storage);
for(auto &req : requests)
{
if(req.size() == 1)
{
jigecha(0, req[0], 0, 0);
}
else if(req.size() == 2)
{
crane(req[0]);
}
else
{
/* Do Nothing */
}
}
return answer;
}경계조건 검사를 사용한 코드
더보기
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<vector<int>> pushed;
int answer = 0;
void printStorage(vector<string> &storage)
{
for(auto &str : storage)
{
cout << str << "\n";
}
cout << "\n";
}
// BFS for each Forklift Req
void forklift(char target, vector<string> &storage)
{
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
// Initialize pushed array
pushed = vector<vector<int>>(storage.size(), vector<int>(storage[0].size(), 0));
// Initialize searching queue
queue<pair<int, int>> qu;
for(int cqu = 0; cqu < storage[0].size(); cqu++)
{
qu.push({0, cqu});
pushed[0][cqu] = 1;
if(storage.size()-1 > 0)
{
qu.push({storage.size()-1, cqu});
pushed[storage.size()-1][cqu] = 1;
}
}
for(int rqu = 1; rqu < storage.size()-1; rqu++)
{
qu.push({rqu, 0});
pushed[rqu][0] = 1;
if(storage[0].size()-1 > 0)
{
qu.push({rqu, storage[0].size()-1});
pushed[rqu][storage[0].size()-1] = 1;
}
}
// BFS
pair<int, int> fr;
while(!qu.empty())
{
int r, c;
fr = qu.front(); qu.pop();
r = fr.first;
c = fr.second;
if(storage[r][c] == '0')
{
for(int d=0; d<4; d++)
{
int nr = r + dr[d];
int nc = c + dc[d];
//Exception : Out of boundary
if(nr < 0 || nr >= storage.size() || nc < 0 || nc >= storage[0].size()) continue;
//Exception : Already pushed
if(pushed[nr][nc] == 1) continue;
if(storage[r][c] == '0')
{
qu.push({nr, nc});
pushed[nr][nc] = 1;
}
}
}
else if(storage[r][c] == target)
{
answer --;
storage[r][c] = '0';
}
}
// printStorage(storage);
return;
}
// Sweep for each Crane Req
void crane(char target, vector<string> &storage)
{
// [Sweep] Check All cells
for(int r=0; r<storage.size(); r++)
{
for(int c=0; c<storage[r].size();c++)
{
// [Main Action] Check (r, c) holds 'target'
if(storage[r][c] == target)
{
storage[r][c] = '0';
answer--;
}
}
}
// printStorage(storage);
return;
}
// solution
int solution(vector<string> storage, vector<string> requests) {
answer = storage.size() * storage[0].size();
for(auto &req : requests)
{
if(req.size() == 1)
{
// cout << "forklift:" << req[0] << "\n";
forklift(req[0], storage);
}
else if(req.size() == 2)
{
// cout << "crane:" << req[0] << "\n";
crane(req[0], storage);
}
else
{
/* Do Nothing */
}
}
return answer;
}🚨 교훈
- 백트래킹을 하는 맥락에서 return과 continue 중 맥락에 알맞은 동작이 무엇인지 생각해보자
- visited / 무효화 표시의 조건을 정확히 짚어야 헤메지 않는다
💭 후기
역시 부트캠프에서 급하게 배운 "생계형 개발자 행동"은
끝없는 공부와 복기를 통해서만 개선될 수 있는 것 같습니다.
원래 같았으면 패딩해서 TC All Pass 보고 그냥 넘어갔을건데
블로그에 포스팅한다고 굳이굳이 다른 방법도 사용해서 고생은 좀 했지만
그래도 근딜/원딜 밸런스가 조금 더 좋아지는 것 같아서 기분은 좋네요.^^
'개발자 일상 > 직장인도 코딩 테스트를 준비합니다' 카테고리의 다른 글
| [프로그래머스 풀이] 비밀 코드 해독(Lv2) - (C++)백트래킹 문제는 포기 조건 검사가 종료 히트 보다 먼저! (4) | 2025.07.27 |
|---|---|
| [프로그래머스 풀이] 유연근무제(Lv1) - (C++)에헤이.. 3년차가 이런 실수를! (4) | 2025.07.26 |