백준 20055번: 컨베이어 벨트 위의 로봇(C++ 풀이 #2 - Linked List 사용)

백준 20055번: 컨베이어 벨트 위의 로봇(C++ 풀이 #2 - Linked List 사용)

저번 글에 이어서...

문제에서의 조건은 저번 글을 참조하자.

저번 글에서는 컨베이어 벨트가 돌아가고 있고, 그 위에서 로봇이 움직이는 상황을 1차원 배열로 구현하였다.

그러고 시간 초과가 떠서 3일동안 계속 삽질했는데, 그 과정에서 최대한 시간을 줄여보려 하다가 이번에 후술할 풀이가 나왔다. 물론 시간이 1초에서 터지는 문제의 원인은 이게 아니라 다른 거긴 했다. 그것도 굉장히 사소하면서 작은 부분...

Linked List 공부한지 얼마 안 되기도 했고... 애초에 포인터를 쓰는 개념이다보니 체계적으로 구상하려고 하는 데에만 3시간정도 쏟고, 그 후에 1시간 정도의 시간동안 코드를 짰던 것 같다. 머리로만 구현하면 도저히 이건 감당할 수가 없겠어서 아이패드 손필기의 힘을 빌렸다. 그래도 이 글을 읽는 사람들이 내가 했던 삽질들을 보면서 Linked List의 활용에 대해 같이 공부해보면 좋을 것 같다.

밑에 보이는게 내가 아이패드로 짜놓은 이 소스코드의 개요이다.

구상

● 단방향 Linked-List로 구현 시도

단방향으로 생각했다가 쌍방향으로 가기로 한 흔적

처음에는 일반적인 Linked-List로 구현하려고 하였다. 즉, Node라는 구조체의 구성요소로 int형인 data 변수와 Node*형인 next를 선언한 것이다.그러고 다시 문제를 보니 문제에서는 data 부분도 내구도를 나타낼 int값과 로봇이 있는지 없는지를 따지는 bool값이 있어야겠다 판단하여, data 변수는 내구도값으로 생각하고 그 뒤에 'bool robot;'을 붙여주기로 했다.

그림으로 정리하면 대충 이렇다.

struct Node{ int data; bool robot; Node* next; };

Linked-List는 이런 노드들을 비엔나 소세지처럼 줄줄이 잇는 거니까, 그 모양을 생각해보면 밑에 있는 것처럼 진짜 소세지 모양이 나온다.

제일 왼쪽에 보이는 것이 가장 최근에 할당된 녀석이고, 제일 오른쪽에 있는 것이 가장 먼저 들어온 녀석이며, 제일 오른쪽 노드의 next는 NULL을 가리키고 있다. 그리고 제일 최근에 할당된 노드를 가리키고 있는 노드 포인터로 전역변수 공간에 list를 선언해주었다.

문제에서 입력부를 만들 때는 1부터 2N까지의 순서로 받는다. 그러면 맨 왼쪽에 오는 애의 data값은 A 2N 이고, 맨 오른쪽에 오는 애의 data값은 A 1 인 것을 알 수 있다.

Linked-List는 저 소세지 앞뒤로 노드를 추가하는 것에 있어서는 매우 효율적이다(더 유식한 말이 있을 텐데... 지식의 한계로 이렇게밖에 설명할 수밖에 없다는 점 양해 부탁...ㅎ). 주소 하나 파놓고 거기다가 값 집어넣은 다음에 포인터로 이어주는 과정 한 번이면 되기 때문이다. 그렇지만 중간에 끼어있는 노드 참조는 무조건 list(위에 그림에 있는 포인터)가 가리키고 있는 노드부터 시작해서 중간에 끼어있는 노드의 인덱스까지 탐색을 해야 한다. 비효율적이다. 그러다 생각한게, '전역변수로 포인터를 더 만들면 되지!'였다. 어차피 우리가 필요한 건 로봇을 올릴 위치와 로봇을 내릴 위치이다. 그렇기 때문에 총 2N개를 입력받는 main함수의 for문에서 i=0일 때의 list를 로봇을 올릴 위치의 포인터(load_point)로 지정해주고, i=N-1일 때의 list를 로봇을 내릴 위치의 포인터(unload_point)로 지정해준다.

그림을 보면 더 이해가 쉬울 것 같다. 위에 내가 필기로 올려놓은 사진도 참고하면 좋다.

이 포인터 두 개를 어떻게 활용할 것이냐?

일단 하나하나 길게 쓰기 귀찮으니까 설명의 편의상 load-point를 LP로, unload-point를 UP로 일단 줄여 말하겠다.

문제에서 말한 것과 같이 시계방향으로 컨베이어 벨트가 한번 돈다고 하면, 위에 있는 그림처럼 LP, UP, list가 바뀌어야 한다. 그걸 다시 Linked-List 모양으로 정리해서 보면

이렇게 되는데, 여기서 보면 '세 포인터가 전부 오른쪽으로 한칸씩 이동한 것' == '시계방향으로 컨베이어 벨트 이동'임을 알 수 있다.

잠시만, LP는?

그래서 오른쪽과 왼쪽을 이어준 것이다. 줄로 되어있는 비엔나 소세지로 목걸이 만드는 과정과 비슷하다고 보면 될 것 같다.

void bind(){ load_point->next = list; }

암튼 일단 여기까지 컨베이어 벨트를 구현하였다.

그 다음 이야기할 건, 저번에 배열로 풀 때에도 언급한 문제에서 이야기하는 "1단계"의 구성이다.

1. 시계방향으로 한칸씩 돌아간다 → rotate 함수 생성

2. 로봇이 움직인다 → robot_move 함수 생성

3. 로봇을 올린다 → load 함수 생성

※ 로봇이 내리는 위치에 있다면, 그 즉시 바로 로봇을 내린다 → unload 함수 생성

그치만... Linked-List 특성 상 함수를 몇 개 더 만들기로 했다.

1. init 함수 : Linked-List를 초기 상태로 돌려주는, 그러니까 연결된 화살표들 다 끊어주는 함수

2. bind 함수 : Linked-List의 오른쪽과 왼쪽을 이어주는 함수

3. add 함수 : 노드를 추가해주는 함수

bind 되어있는 상황에서 나머지는 기존에 Linked-List 코드 짜던 방식과 크게 차이가 없는데, init 함수는 그대로 NULL까지 돌리라고 했다가 에러가 날 것이 분명하기 때문에(bind 되면 NULL을 가리키는 포인터가 없으니까) 제일 나중에 추가된 노드에 도착할 때까지 돌리고 반복문을 종료하기로 하였다. 그런데 처음 시작 위치가 제일 나중에 추가된 노드인데? 하고 생각해보니 do-while문을 쓰면 되는 거였더라고.

void init(){ if(list==NULL) return ; else{ Node* last_point = list; Node* cur = list; do{ list = cur->next; delete cur; cur = list; }while(cur!=last_point && cur!=NULL); } }

init, bind, add 이렇게 셋은 컨베이어 벨트를 구현하는 친구들이기 때문에 rotate부터 load까지 반복되는 while문보다 앞에 위치해야 한다. 따라서 정리하면 main 함수의 전반적인 흐름은 "init→bind→입력부(add 포함)→while문{rotate→robot_move→load}→출력부"이다.

문제가 일어난 부분은 robot_move 함수를 짤 때였다.

먼저 들어온 로봇부터 움직일 수 있다고 했으므로, Linked-List에서 노드는 UP에서부터 LP로 로봇이 있는지 없는지부터 체크를 하고, 오른쪽 노드에 로봇이 있는지 없는지와 내구도가 1 이상인지 체크를 해야 한다. 그런데 단방향 Linked-List는 노드 포인터 list가 움직이는 방향이 무조건 2N-1번째 노드부터 0번째 노드까지 움직이고 그 반대방향으로는 움직일 수 없다. 그나마 양 끝이 연결되어있는 위와 같은 상황에서 반대방향으로 한 칸 움직이려면 원래 움직일 수 있는 방향으로 한 바퀴를 빙 돌면 되는데, 그러면 비효율의 끝판왕을 달리기 때문에 애초에 효율성을 추구했던 이번 풀이와 거리가 멀어진다. 그래서 노드에 반대방향에 있는 노드를 가리키는 포인터를 추가하여 새로 코드를 구성하기로 했다. 그게 이 글에서 내가 말하는 쌍방향 Linked-List이다.

● 쌍방향 Linked-List로 구현

쌍방향에서는 단방향에서 next로 불리던 노드 포인터를 tail로 바꿔 부르고, 구조체의 앞에 head라는 노드 포인터를 추가하기로 하였다.

그리고 이렇게 노드끼리 이어주면 아까와는 달리 앞뒤로 참조할 수 있는 Linked-List가 만들어진다.

전반적인 흐름은 아까 단방향으로 접근할 때와 거의 똑같다. 각 함수에서 head 부분 처리를 추가하면 되는 일이라 다른 부분은 그렇게 복잡하지 않은데, robot_move 함수에서 주의해야할 게 있다.

빨간 형광펜을 친 부분이 노드의 head 부분이고, 노란 형광펜을 친 부분이 노드의 tail 부분인데, 컨베이어 벨트를 머릿속에 떠올리면서 코드를 짤 때에는 N-1번째부터 0번째에서 head와 tail의 위치를 신경쓰지 않으면 logical error가 생긴다. 실제로도 코드 짜고 돌렸더니 제대로 된 값이 안 나와서 "아... 역시 포인터 쓰는 건 너무 어. 렵. 다!" 하다가 나의 무지를 깨달은 부분이기도 하다.

코드

아이패드로 계속 그림 그리고 스샷 찍어서 설명하다보니 이제 좀 지치려고 한다. 그래도 설명 할 만한 부분은 다 설명했으니 이제 내가 쓴 코드를 올리면 될 것 같다. 저번에 내가 배열로 풀었을 때랑 코드를 비교해보는 것도 재미있을 것 같다.

#include #include using namespace std; struct Node{ Node* head; int data; bool robot; Node* tail; }; Node* list; Node* load_point; Node* unload_point; int zero_cnt; void init(){ if(list==NULL) return ; else{ Node* last_point = list; Node* cur = list; do{ list = cur->tail; delete cur; cur = list; }while(cur!=last_point && cur!=NULL); } } void add(int key){ Node* new_node = new Node; new_node->head = NULL; new_node->data = key; new_node->robot = false; new_node->tail = NULL; if(list==NULL){ list = new_node; } else{ Node* cur = list; cur->head = new_node; list = new_node; new_node->tail = cur; } } void bind(){ load_point->tail = list; list->head = load_point; } void load(){ if(load_point->robot == false && load_point->data >= 1){ load_point->robot = true; --load_point->data; if(load_point->data == 0) ++zero_cnt; } } void unload(){ if(unload_point->robot == true){ unload_point->robot = false; } } void rotate(){ load_point = list; Node* temp_node = unload_point; unload_point = temp_node->tail; list = load_point->tail; unload(); } void robot_move(int N){ Node* searching = unload_point->tail; for(int i = 0; irobot == true){ Node* nnode = searching->head; if(nnode->robot == false && nnode->data >= 1){ searching->robot = false; nnode->robot = true; --nnode->data; if(nnode->data == 0) ++zero_cnt; } } Node* temp_node = searching->tail; searching = temp_node; } unload(); } int main(){ // clock_t start, end; // double result; // start = clock(); cin.tie(); ios::sync_with_stdio(false); int N, K; cin >> N >> K; init(); for(int i = 0; i<2*N; ++i){ int input_A; cin >> input_A; add(input_A); if(i == 0) load_point = list; if(i == N-1) unload_point = list; } bind(); int step_cnt = 0; while(K > zero_cnt){ ++step_cnt; rotate(); robot_move(N); load(); } cout << step_cnt << endl; // end = clock(); // result = (double)(end-start); // cout << result << endl; return 0; }

아... 역시 포인터는 어려워!

from http://dalm.tistory.com/5 by ccl(A) rewrite - 2021-07-27 01:26:21