재원블로그 재원블로그

이 문제는 시뮬레이션 문제이다. 시뮬레이션 문제 특성상 구현이 매우 복잡하지만 일단 구현하면 문제는 풀린다. 문제를 제대로 읽지 않아서 이동 시 범위를 넘어갔을 때 다시 순환형으로 돌아온다는 사실을 모르고 구현했다가 다시 풀었다. 모듈러 연산을 활용하여 연산 횟수를 줄이기 위해서는 인덱스가 1로 시작하면 매우 복잡하다. 따라서 입력을 받을 때 r과 c를 1씩 빼서 0부터 시작하도록 수정하였고, matrix의 한 요소를 벡터로 하여 항상 push 할 수 있도록 하여 구현을 그나마 간단하게 하였다. 어려운 구현 문제는 꼭 함수를 분리하여 추상화를 먼저 하고 순서를 짜놓은 뒤 세부 구현을 하는게 훨씬 간편하다. #include #include #include using namespace std; #define..

이 문제는 bfs 를 이용해서 푸는 문제이다. 처음에는 이 문제를 풀 때 보통 bfs 구현처럼 큐에 push 할 때 visited 를 수정했다. 그러나 이 문제는 그렇게 하면 굉장히 복잡해지고 정답을 맞추기 쉽지 않아진다. 이 문제는 visited 를 큐에서 pop 하자마자 체크하면 간단히 풀리는 문제였다. 또한 visited 를 int 로 하여 최단 거리를 계산하지만, 이 경우 여러 경로를 탐색해야 하므로 bool 로 선언해서 문제를 푸는게 훨씬 간단하다. 너무 정형화된 패턴으로 문제를 풀면 복잡해진다는 교훈을 얻었다. #include #include #include using namespace std; int n, k, answer = -1, cnt; bool visited[100001]; bool ..

이 문제는 강한 연결 요소 (SCC) 를 이용해서 풀 수 있는 문제이다. 사실 이 문제는 dfs 를 약간만 설정해서 사이클의 판단만 해주면 풀리는 문제이다. 그러나 강한 연결 요소를 통해 유향 그래프의 사이클 요소를 찾을 수 있다는 생각이 떠올라 SCC로 풀었다. 이 문제에서 중요한 건 입력으로 주어지는 간선은 outgoing edge가 단 하나라고 명시되어 있지만, transpose graph 에서는 outgoing edge 가 하나가 아니라는 것이다. 그 사실을 망각하고 풀어서 많은 시간을 쏟게 되었다. #include #include #include using namespace std; vector edges; vector transEdges; vector visited; vector tempScc..

이 문제는 bfs 를 이용해서 푸는 문제이다. 이 문제에서 핵심은 섬이 꼭 육지로만 이루어져 있지 않을 수 있다는 것이다. 겉면이 육지로 둘러싸이고 내부는 바다일 수 있는 것이다. 따라서 외곽을 찾아서 bfs 를 돌릴 때 내가 출발한 섬의 번호와 같은 육지에 도착하면 실패하도록 구현해야 한다. 두번째로 bfs2 에서 while 문 내부에서 리턴하지 못하고 모두 끝나고 리턴할 때의 리턴값을 잘 설정해야 한다. 나는 처음에 아무 생각 없이 -1로 놨었는데, 그렇게 하면 최소를 구하는 문제에서 -1이 정답으로 나오는 케이스가 발생할 수 있다. 그러므로 최소를 구하는 문제에서는 리턴값을 가장 크게, 최대를 구하는 문제에서는 리턴값을 가장 작게 설정해줘야 한다. #include #include #include #..

이 문제는 bfs 를 사용하는 문제이다. 처음에는 이 문제에서 DSLR 연산의 리턴값을 string을 이용해서 구현했으나, 그렇게 하면 시간 초과가 발생하였다. 그래서 정수를 리턴하도록 하여 최대한 연산의 수를 줄였고, 정답을 받을 수 있었다. #include #include #include #include #include using namespace std; int operD(int temp) { temp *= 2; temp %= 10000; return temp; } int operS(int temp) { if (temp == 0) { temp = 9999; } else { temp--; } return temp; } int operL(int temp) { int result = (temp % 100..

이 문제는 시뮬레이션 문제로 주어진 순서에 맞춰 구현하면 되지만, 구현이 매우 어렵다. 이 문제에서 가장 어려운 부분은 상어가 움직이는 것인데, 한 상어가 움직인 후 바로 맵에 저장하면 다음 상어가 움직임에서 잘못된 결과가 나오게 된다. 그러므로 모든 상어의 다음 좌표를 따로 저장해둔 뒤, 그 배열을 순회하면서 상어를 맵에 올려놓는 방식으로 구현하면 정답이 나오게 된다. 맵의 경우 구조체로 상어를 만든 뒤, 그 구조체의 2차원 배열로 구현했다. #include #include using namespace std; #define MAX 100 #define UP 1 #define DOWN 2 #define RIGHT 3 #define LEFT 4 typedef struct _shark { int y; in..

이 문제는 시뮬레이션 문제로 주어진 요구사항을 그대로 구현하면 시간 초과 없이 해결할 수 있는 문제이다. 톱니바퀴를 돌리는 구현에 있어서 덱을 사용하여 문제를 해결했다. #include #include #include #include using namespace std; deque gear[4]; #define CLOCK 1 #define COUNTERCLOCK -1 #define N 0 #define S 1 int leftSide(int gearNum) { int temp1 = gear[gearNum].back(); gear[gearNum].pop_back(); int temp2 = gear[gearNum].back(); gear[gearNum].push_back(temp1); return temp2;..

이 문제는 완전 탐색으로 푸는 시뮬레이션 문제이다. 이 문제를 처음 접했을 때는 막막했는데, 한 단계씩 천천히 구현해보니 꽤 쉬운 문제였다. 상하좌우로 움직였을 때 로직을 생각해내는 것이 핵심인데, 나는 이를 큐를 이용해서 구현했다. 또한 전역 배열로 board를 구현하지 않고 이차원 벡터를 매개변수로 주고, 바뀐 벡터를 리턴하는 방식으로 하여 더 쉽게 구현할 수 있었다. #include #include #include #include using namespace std; #define MAX 20 int n; int answer = -1; vector up(vector& board) { vector result(n, vector(n, 0)); for (int x = 0; x < n; x++) { que..