문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60061
[2020 카카오 블라인드]에서 나왔던 문제.
너무 생각을 복잡하게 하고, 이상하게 해서 오래 걸렸다.
문해력이 부족한 탓일까?
문제 핵심 및 풀이
제한 사항 분석
제한사항을 보면 n은 최대 100이기 때문에, 100x100이 한계이다.
또한 build_frame이라는 구조물의 설치/삭제 커맨드는 최대 1000개까지 들어온다.
100x100x1000 = 10^7 으로 완전탐색을 해도 상관이 없다.
구조물을 어떻게 표현할 것인가?
이것도 나름 생각이 필요했다.
문제에서 기둥은 위로 설치하고, 보는 오른쪽으로 설치한다고 했다.
그래서 이를 설치가 시작된 곳의 좌표로, 구조물을 표현했다.
예를 들어서, 위에서 표시한 부분을 나타내보면
map(1,0) = 기둥
map(1,1) = 보
map(2,1) = 기둥
이런 식으로 표기할 것이다.
이 문제에서는 "해당 좌표 부분이 채워졌는가?" 의 참/거짓 유무만 확인하면 된다.
그러므로 2차원 배열을 쓰는 bool형을 사용했다.
여기서 한 가지 중요한 것은 이런 경우가 나올 수 있다는 것이다.
위 같은 경우 map(1,1)에 기둥과 보가 동시에 들어간다.
그럼 어떻게 해야 할까?
map을 3차원으로 만들어서 해도 괜찮지만,
나는 그냥 좀 더 직관적으로 보기 위해,
기둥과 보를 위한 2차원 bool 배열을 따로 만들었다.
즉 2개의 2차원 배열을 통해 문제를 해결한다.
기둥의 설치
이제 기둥과 보를 따로 구분하여 고려해 보자.
기둥을 설치할 때 어떤 경우에 설치할 수 있을까?
여기서 관점은 설치하는 기둥에만 두고,
이미 놓여있는 구조물들은 정상이라고 가정한다.
보 밑에 빈 부분은 구조물이 동작가능 하도록 되어있다는 전제 하에 생략하였다.
그리고 여기선 (x, y)는 (가로축, 세로축)으로 해석한다.
또한 해당 기둥을 (x, y)에 설치한다는 뜻이다.
1. 땅에 설치할 때 → ( map [x][y]에서 y == 0 )
2. 다른 기둥 위에 설치할 때 → ( map [x][y-1]에 기둥이 있을 때 )
3. 보의 시작지점에 있을 때 → ( map [x][y]에 보가 있을 때 )
4. 보의 끝지점에 있을 때 → ( map [x-1][y]에 보가 있을 때 )
이 경우를 제외하고는 모두 설치 불가능하다고 보면 된다.
보의 설치
일단 문제에서 보는 땅에 설치할 수 없다고 했기 때문에,
y == 0 일 때는 제외한다.
1. 보의 끝점에 기둥이 있는 경우 → ( map [x+1][y-1]에 기둥이 있을 때 )
2. 보의 시작지점에 기둥이 있는 경우 → ( map [x][y-1]에 기둥이 있을 때)
3. 보의 양쪽(시작점과 끝점)에 다른 보가 있을 때 → ( map [x-1][y] == 보 && map [x+1][y] == 보)
위의 경우를 제외하곤, 모두 설치가 안된다.
기둥과 보의 삭제 가능 유무
기둥과 보가 삭제가 가능한지는
제한사항에서 힌트를 얻어 완전탐색을 사용했다.
삭제를 확인하는 데에는 다음과 같은 로직을 따른다,
1. 일단 커맨드로 들어온 좌표에서 기둥/보를 삭제한다.
2. 완전 탐색을 통해 전체 (n+1) x (n+1)을 모두 돌면서
보를 만나면, 보를 설치할 때와 같은 조건으로 체크한다.
기둥을 만나도 마찬가지이다.
3. 하나라도 false 즉, 설치할 때의 조건과 맞지 않는다면
그 삭제는 가능하지 않은 것으로 판단한다.
4. 삭제했던 좌표에 기둥/보를 추가한다.
위와 같은 방식을 통해 해결할 수 있다.
실수하기 쉬운 부분
이 문제에서는 특히나 실수할 수 있는 부분이 많은데
첫 번째로, 입력 좌표가 [가로, 세로]로 되어있기 때문에 혼동되기가 쉽다.
이를 위해서 처음에 x와 y를 치환하던가 하는 방식을 사용해도 좋다.
두 번째로 out of bound이다.
위에서 보면 x-1이 들어가는 곳이 있는데, x = 0 일 때 예외가 발생해 버린다.
그래서 이 부분을 처리해 주는 로직이 필요하다.
마지막으로, 가로 좌 표를 기준으로 정렬해야 하고,
둘 다 같은 경우 보 보다 기둥이 먼저 나와야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool col[105][105] = {false,}; // 기둥 체크 배열
bool bo[105][105] = {false,}; // 보 체크 배열
int mapSize; // 맵의 크기 n+1
// 현재 기둥이 설치 가능한 상태인가?
bool canColAction(int x, int y){
// y == 1인 이유는 x-1때문에 0 아래로 내려가지 않도록 전체적으로 +1을 해줌
if(y == 1 || col[x][y-1] || bo[x-1][y] || bo[x][y]) return true;
return false;
}
// 현재 보가 설치 가능한 상태인가?
bool canBoAction(int x, int y){
if((col[x][y-1] || col[x+1][y-1])
|| (bo[x-1][y] && bo[x+1][y])) return true;
return false;
}
// 삭제할수 있는가?
bool canDelete(){
//전체 맵을 순회(완전 탐색)
for(int i = 1; i <= mapSize+1; i++){
for(int j = 1; j <= mapSize+1; j++){
// 해당 좌표에 기둥이 있지만 설치가 불가능할때
if(col[i][j] && !canColAction(i,j)) return false;
// 해당 좌표에 보가 있지만 설치가 불가능할 때
if(bo[i][j] && !canBoAction(i,j)) return false;
}
}
return true;
}
// 설치 함수
void build(int x, int y, int type){
switch(type){
// 설치 가능 상태일때 설치
case 0:
if(canColAction(x,y)) col[x][y] = true;
break;
case 1:
if(canBoAction(x,y)) bo[x][y] = true;
break;
}
}
// 제거 함수
void remove(int x, int y, int type){
switch(type){
case 0:
col[x][y] = false; // 미리 제거
// 삭제할 수 없는 것이었으면 다시 추가
if(!canDelete()) col[x][y] = true;
break;
case 1:
bo[x][y] = false;
if(!canDelete()) bo[x][y] = true;
break;
}
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
mapSize = n+1; // 오른쪽이랑 위로 가는 것이기 때문에 사실상 +1이 더 필요
for(auto frame : build_frame){
// x-1연산은 편하게 해주기 위해 전체 인덱스를 1씩 더해줌
if(frame[3] == 1) build(frame[0]+1,frame[1]+1,frame[2]);
else remove(frame[0]+1,frame[1]+1,frame[2]);
}
// 결과 담기
// 순회를 이미 정렬된 순서로 하기 때문에 정렬이 따로 필요가 없음
for(int i = 1; i <= n+1; i++){
for(int j = 1; j <= n+1; j++){
// 해당 좌표에서 담을 때 더해줬던 1을 빼준 상태로 추가
if(col[i][j]) answer.push_back({i-1,j-1,0});
if(bo[i][j]) answer.push_back({i-1,j-1,1});
}
}
return answer;
}
Java 구현 코드
↓
import java.util.*;
class Solution {
boolean[][] col; // 기둥 체크 배열
boolean[][] bo; // 보 체크 배열
int size; // 맵의 크기
public int[][] solution(int n, int[][] build_frame) {
int[][] answer;
size = n;
List<int[]> ans = new ArrayList<>();
col = new boolean[n+2][n+2]; // 크기만큼 초기화
bo = new boolean[n+2][n+2]; // 크기만큼 초기화
// 전체 배열 초기화
for(int i = 0; i <= n+1; i++)
for(int j = 0; j <= n+1; j++) {
col[i][j] = false;
bo[i][j] = false;
}
for(int[] frame : build_frame){
if(frame[3] == 1)
// x-1연산은 편하게 해주기 위해 전체 인덱스를 1씩 더해줌
build(frame[0]+1,frame[1]+1,frame[2]);
else
delete(frame[0]+1,frame[1]+1,frame[2]);
}
// 결과 담기
// 순회를 이미 정렬된 순서로 하기 때문에 정렬이 따로 필요가 없음
for(int i = 1; i <= n+1; i++){
for(int j = 1; j <= n+1; j++){
// 해당 좌표에서 담을 때 더해줬던 1을 빼준 상태로 추가
if(col[i][j]) ans.add(new int[]{i-1,j-1,0});
if(bo[i][j]) ans.add(new int[]{i-1,j-1,1});
}
}
answer = new int[ans.size()][3];
for(int i = 0; i < ans.size(); i++){
answer[i] = ans.get(i);
}
return answer;
}
// 설치 함수
public void build(int x, int y, int type){
switch(type){
// 설치 가능한 상태일때 설치
case 0:
if(canColAction(x,y)) {
col[x][y] = true;
}
break;
case 1:
if(canBoAction(x,y)) {
bo[x][y] = true;
}
break;
}
}
// 삭제 함수
public void delete(int x, int y, int type){
switch(type){
case 0:
col[x][y] = false; // 미리 제거
// 삭제할 수 없는 것이었으면 다시 추가해둠
if(!canDelete()){
col[x][y] = true;
}
break;
case 1:
bo[x][y] = false;
if(!canDelete()){
bo[x][y] = true;
}
break;
}
}
// 현재 기둥이 설치 가능한 상태인가?
public boolean canColAction(int x, int y){
// y == 1인 이유는 x-1때문에 0 아래로 내려가지 않도록 전체적으로 +1을 해줌
if(y == 1 || col[x][y-1]) return true;
if(bo[x][y] || bo[x-1][y]) return true;
return false;
}
// 현재 보가 설치 가능한 상태인가?
public boolean canBoAction(int x, int y){
if(col[x][y-1] || col[x+1][y-1]) return true;
if(bo[x+1][y] && bo[x-1][y]) return true;
return false;
}
// 현재 보가 설치 가능한 상태인가?
public boolean canDelete(){
// 전체 맵 순회(완전 탐색)
for(int i = 1; i <= size+1; i++){
for(int j = 1; j <= size+1; j++){
// 해당 좌표에 기둥이 있지만 설치가 불가능할때
if(col[i][j] && !canColAction(i,j)) return false;
// 해당 좌표에 보가 있지만 설치가 불가능할 때
if(bo[i][j] && !canBoAction(i,j)) return false;
}
}
return true;
}
}↑
시행착오
문제 조건을 잘못 읽어서 이틀을 썼다.
분명 인터넷에 있는 글과 로직이 같은데 왜 나만 틀렸다고 나오지? 했는데,
"x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다."
이 조건이 난 x, y좌표가 같은 맵에서 보와 기둥이 둘 다 있는 경우,
기둥만 출력하라는 건 줄 알았다..
지금 보니까 왜 헷갈렸지
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me