Computer Science & Engineering

https://programmers.co.kr/learn/courses/30/lessons/60063

풀이

    이 문제는 DFS, BFS 모두 풀이가 가능한 문제이다. 글쓴이는 평소 DFS를 많이 이용했기 때문에 이번에는 BFS를 이용하여 풀어보았다. 로봇이 한 칸을 차지하는 것이 아닌 두 칸을 차지하므로 예외처리를 많이 해야하기 때문에 캐치하지 못한 부분이 있어 일부 테스트 케이스를 통과하지 못할 수도 있다. 나도 이 문제를 풀며 내가 생각하지 못한 부분을 예외처리하지 못하여 약간의 시간이 더 걸렸다. 로봇의 현재 위치에서 생각해야할 부분은 네 가지가 있다.

1. 다음 위치가 보드를 벗어나는지
2. 로봇이 차지하는 두 칸 중 하나도 1이 아닌지
3. 이미 현재 위치를 거쳐갔는지
4. 회전하는 경우 회전할 때 지나가는 칸이 1이 아닌지

위 네 가지만 예외처리하면 쉽게 풀 수 있는 문제이다. 예외처리만 하면 되는 문제이기 때문에 if, continue 등이 많이 쓰였다.

    문제를 풀 때 로봇이 상하좌우로 이동하는 경우, 회전하는 경우를 나누어서 풀었다. 상하좌우로 이동하는 경우는 일반 BFS처럼 풀면 되기 때문에 예외처리가 따로 할 부분이 없었다. 문제는 회전하는 경우였다. 회전하는 경우를 차지하는 두 칸 중에 한 칸이 대각선으로 이동하는 방식으로 생각했다. 그림으로 나타내면 다음과 같다.

위와 같이 이동한다고 할 때 실제로는 2, 4번으로 이동할 수 있지만 1, 3번으로는 이동하지 못한다. 이 부분을 예외처리하기 위해 두 칸의 x좌표나 y좌표 중 하나가 같은 경우에만 올바르게 회전했다고 판단했다. 이 과정을 다른 쪽 칸도 똑같이 진행하였다. 이렇게 회전하는 경우에 갈 수 있는 좌표의 위치를 계산할 수 있다.

소스 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct pos{ //x, y좌표를 가지는 구조체
    int x, y;
};

struct element { //큐에 넣을 구조체
    pair<pos,pos> position;
    int depth;
};

bool visit[101][101][101][101]; //방문배열

int dx[4] = {1, 0, 0, -1}; //dx, dy는 상하좌우로 이동
int dy[4] = {0, 1, -1, 0};
int rx[4] = {1, 1, -1, -1}; //rx, ry는 회전
int ry[4] = {1, -1, 1, -1};

int solution(vector<vector<int>> board) {
    int N = board.size();
    pair<pos,pos> robot = {{0, 0}, {0, 1}}; ///로봇의 현재 위치
    queue<element> q; //BFS에 사용될 큐
    
    q.push({robot, 0}); //현재 위치를 큐에 넣음
    visit[robot.first.x][robot.first.y][robot.second.x][robot.second.y] = true; //현재 위치 방문 표시
    visit[robot.second.x][robot.second.y][robot.first.x][robot.first.y] = true; //두 칸을 반대로 했을 때도 방문 표시
    
    while(!q.empty()) { //큐가 빌 때까지
        element e = q.front(); q.pop();
        pair<pos,pos> now = e.position; //현재 위치
        for(int d = 0; d < 4; d++) { //상하좌우 방향으로
            pair<pos,pos> nxt = {{now.first.x + dx[d], now.first.y + dy[d]}, {now.second.x + dx[d], now.second.y + dy[d]}}; //다음 좌표 위치
            if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 건너뛰기
            if(nxt.first.y < 0 || nxt.first.y >= N) continue;
            if(nxt.second.x < 0 || nxt.second.x >= N) continue;
            if(nxt.second.y < 0 || nxt.second.y >= N) continue;
            if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //만약 두 칸 중에 하나라도 1인 경우 건너뛰기
            if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue; //이미 방문한 경우도 건너뛰기
            if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue; //로봇 왼쪽 오른쪽이 반대로 됐을 경우도 같음
            if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //도착한 경우 방문 횟수 리턴
                return e.depth + 1;
            }
            else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
                visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
                visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
                q.push({nxt, e.depth + 1});
            }
        }
        
        
        for(int r = 0; r < 4; r++) { //회전하는 경우
            pair<pos,pos> nxt = {{now.first.x + rx[r], now.first.y + ry[r]}, {now.second.x, now.second.y}}; //한 쪽 날개 회전 
            if(nxt.first.x != nxt.second.x && nxt.first.y != nxt.second.y) continue; //만약 한쪽을 대각선으로 회전했을 때 로봇이 차지하는 두 칸이 나란히 있지 않은 경우 건너뛰기
            if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 건너뛰기
            if(nxt.first.y < 0 || nxt.first.y >= N) continue;
            if(nxt.second.x < 0 || nxt.second.x >= N) continue;
            if(nxt.second.y < 0 || nxt.second.y >= N) continue;
            if(board[now.first.x][now.first.y + ry[r]] || board[now.first.x + rx[r]][now.first.y]) continue; //회전시 지나가는 칸이 1인 경우 건너뛰기
            if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //차지하는 두 칸중 하나라도 1인 경우 건너뛰기
            if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue; //이미 방문한 경우 건너뛰기
            if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue;
            
            if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //종료지점 도착시 리턴 
                return e.depth + 1;
            }
            else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
                visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
                visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
                q.push({nxt, e.depth + 1});
            }
        }
            
        for(int r = 0; r < 4; r++) { //다른 한 쪽이 회전하는 경우
            pair<pos,pos> nxt = {{now.first.x, now.first.y}, {now.second.x + rx[r], now.second.y + ry[r]}}; //다른 한 쪽 날개 회전
            if(nxt.first.x != nxt.second.x && nxt.first.y != nxt.second.y) continue; //로봇이 차지하는 두 칸이 나란히 있지 않은 경우 리턴
            if(nxt.first.x < 0 || nxt.first.x >= N) continue; //범위를 벗어나는 경우 리턴
            if(nxt.first.y < 0 || nxt.first.y >= N) continue;
            if(nxt.second.x < 0 || nxt.second.x >= N) continue;
            if(nxt.second.y < 0 || nxt.second.y >= N) continue;
            if(board[now.second.x][now.second.y + ry[r]] || board[now.second.x + rx[r]][now.second.y]) continue; //회전시 지나가는 칸이 1인 경우 건너뛰기
            if(board[nxt.first.x][nxt.first.y] || board[nxt.second.x][nxt.second.y]) continue; //차지하는 두 칸중 하나라도 1인 경우 건너뛰기
            if(visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y]) continue;//이미 방문한 경우 건너뛰기
            if(visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y]) continue;
            
            if((nxt.first.x == N-1 && nxt.first.y == N-1) || (nxt.second.x == N-1 && nxt.second.y == N-1)) { //종료지점 도착시 리턴
                return e.depth + 1;
            }
            else { //그렇지 않은 경우 다음 로봇 위치 방문 표시 후 큐에 넣기
                visit[nxt.first.x][nxt.first.y][nxt.second.x][nxt.second.y] = true;
                visit[nxt.second.x][nxt.second.y][nxt.first.x][nxt.first.y] = true;
                q.push({nxt, e.depth + 1});
            }
        }
    }
}

같은 코드가 반복되어 비효율적인 부분이 있긴 하지만 프로그램 자체가 길지 않으므로 하나의 함수에 작성하였다.시간의 효율성을 생각해보면 큐 안의 반복문이 4번 반복하는 for문이 3개 있으므로 배열의 크기를 N이라고 할 때 약 N * N * 12번의 반복이 발생하지만 12번의 반복은 10^8이 약 1초 걸린다고 생각할 때 무시해도 될 정도의 아주 작은 시간이므로 그다지 효율성을 떨어뜨리지 않는다고 할 수 있다.

채점 결과

https://programmers.co.kr/learn/courses/30/lessons/42892

문제 설명

이 문제는 좌표로 주어지는 노드들을 트리로 이진 트리로 만들어 전위 순회, 후위 순회 결과를 리턴하는 문제이다. 예시는 다음과 같다.

첫 번째 그림과 같이 주어진 좌표를 아래의 그림처럼 이진 트리 구조로 만드는 것이다. 트리를 구성하는 노드들의 규칙은 다음과 같다.

1. 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
2. 모든 노드는 서로 다른 x값을 가진다.
3. 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
4. 자식 노드의 y 값은 항상 부모 노드보다 작다.
5. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
6. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

위 예시의 전위 순회와 후위 순회의 결과는 다음과 같이 나온다.

• 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
• 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7

풀이

이 문제를 풀기 위해서 우선 트리를 구현해야한다. 연결리스트를 이용하여 구현하면 복잡해진다고 판단하여 배열을 이용하였다.

1. 트리의 표현

    pair<int,int>로 구성된 배열을 이용하여 first에는 왼쪽 자식, second에는 오른쪽 자식의 번호를 저장하였다. 트리를 사용하기 위해서는 트리를 초기화해야한다. 자식을 가리키는 인덱스 번호가 자기 자신과 같다면 리프노드로 판단하도록 초기화하였다.

2. 노드 순서

    입력으로 주어진 노드 정보들을 루트 노드부터 순서대로 정렬해야한다. 이때 주어진 배열의 (인덱스 번호 + 1)이 노드의 번호이기 때문에 주어진 배열 자체를 정렬시키면 안되고 인덱스 번호와 좌표를 유지해야한다. 따라서 각 노드의 번호를 통해 좌표를 쉽게 찾기 위해 map을 사용하였고 전위 순회 방식으로 노드를 정렬하기 위해 정렬을 위한 node라는 배열을 따로 선언하였다.

3. 트리 구현

    그 다음에는 정렬된 노드를 순서대로 트리에 붙여나가야한다. 트리를 만드는 find함수를 따로 구현하였다. find 함수는 다음과 같이 동작한다.

1. 현재 노드의 x좌표보다  추가하는 노드의 x좌표가 작은 경우(왼쪽 자식인 경우)
   • 만약 왼쪽 자식이 자기 자신일 때(리프노드일 때) 왼쪽 자식에 붙인다.
   • 그렇지 않으면 재귀적으로 왼쪽 자식과 현재 노드를 방금 과정과 똑같이 비교한다.
2. 현재 노드의 x좌표보다 추가하는 노드의 x좌표가 큰 경우(오른쪽 자식인 경우)
   • 만약 오른쪽 자식이 자기 자신일 때(리프노드일 때) 오른쪽 자식에 붙인다.
   • 그렇지 않으면 재귀적으로 오른쪽 자식과 현재 노드를 방금 과정과 똑같이 비교한다.

4. 전위 순회와 후위 순회

    전위 순회는 왼쪽 오른쪽 자식을 탐색하기 전에 자기 자신을 경로에 넣으면 된다. 반대로 후위 순회는 왼쪽 오른쪽 자식을 탐색하고 난 이후에 자기 자신을 경로에 넣으면 된다.

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

pair<int,int> tree[10001];
map<int,pair<int,int>> m;

vector<int> frontpath; //전위순회 경로
vector<int> endpath; //후위순회 경로

struct edge { //정렬을 위한 구조체
    int idx, x, y;
};

bool cmp(edge a, edge b) { //루트노드부터 순서대로 정렬하는 비교함수
    if(a.y == b.y) {
        return a.x < b.x;
    }
    else
        return a.y > b.y;
}

void find(int now, edge e) { //적절한 위치 찾기
    pair<int,int> nowpos = m[now];
    if(nowpos.first > e.x) { //왼쪽자식인 경우
        if(tree[now].first == now) { //왼쪽 자식 끝인 경우
            tree[now].first = e.idx; //왼쪽 자식에 붙이기
            return;
        }
        else { //끝이 아닌 경우
            find(tree[now].first, e); //재귀적으로 탐색
        }
    }
    else { //오른쪽 자식인 경우
        if(tree[now].second == now) { //오른쪽 자식 끝인 경우
            tree[now].second = e.idx;
            return;
        }
        else {
            find(tree[now].second, e);
        }
    }
    return;
}

void front(int now) { //전위순회
    frontpath.push_back(now); //경로 먼저 추가
    if(tree[now].first != now) { //리프노드가 아니라면
        front(tree[now].first); //왼쪽 자식 탐색
    }
    if(tree[now].second != now) {//리프노드가 아니라면
        front(tree[now].second); //오른쪽 자식 탐색
    }
}

void end(int now) { //후위순회
    if(tree[now].first != now) { //리프노드가 아니라면
        end(tree[now].first); //왼쪽 자식 탐색
    }
    if(tree[now].second != now) { //리프노드가 아니라면
        end(tree[now].second); //오른쪽 자식 탐색
    }
    endpath.push_back(now); //경로 나중에 추가
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    vector<edge> node; //정렬을 위한 배열
    
    for(int i = 1; i <= nodeinfo.size(); i++) { //트리 초기화
        tree[i].first = i; //왼쪽 자식을 자기 자신으로
        tree[i].second = i; //오른쪽 자식을 자기 자신으로
    }
    
    for(int i = 0;i < nodeinfo.size(); i++) { 
        node.push_back({i+1, nodeinfo[i][0], nodeinfo[i][1]}); //정렬을 위한 배열
        m[i+1] = {nodeinfo[i][0], nodeinfo[i][1]}; //각 노드 번호별 x, y좌표 map에 저장
    }
    sort(node.begin(), node.end(), cmp); //y좌표가 큰순, x좌표가 작은순으로 정렬
    
    int root = node[0].idx; //루트 인덱스 번호
    
    for(int i = 1; i < node.size(); i++) {
        edge now = node[i]; //현재 노드
        find(root, now); //자식으로 붙이기
    }
    
    front(root); //전위순회
    end(root); //후위순회
    
    
    answer.push_back(frontpath);
    answer.push_back(endpath);
    
    return answer;
}

결과