알고리즘매일매일

https://www.acmicpc.net/problem/17822

원판을 회전시키며 인접한 수를 비교하고, 같다면 숫자를 지우는 작업을 반복하는 시뮬레이션 문제이다.

T회만큼 반복하면서 x의 배수인 원판들을 모두 회전시킨 후 인접한 같은 수를 저장해놓았다가 나중에 한 번에 지워준다. (미리 지워서 0으로 만들어버리면 다른 방향으로 인접한 수를 지울 수 없다)

인접한 수 중 같은 숫자인게 없다면 원판에 있는 숫자의 평균을 구해서 평균보다 작으면 1을 증가시켜주고 크면 1을 감소시킨다. 여기서 지워진 숫자는 제외하고 평균을 구해야 한다

//k칸만큼 회전시키기

먼저 k칸만큼 시계방향 회전시킨 방법은 아래와 같이 했다. 예를 들어 k가 4인 경우이다.

편의상 배열은 인덱스가 1부터 시작하도록 구현했다.

원래 원판에 있던 숫자를 첫 번째부터 tmp배열의 k만큼 떨어진 곳인 5번 자리부터 복사한다. 인덱스가 배열 밖으로 넘어가면 안 되므로 작업을 tmp배열의 마지막 부분인 6번 인덱스까지만 먼저 진행한다.

그다음 아래 그림처럼 원판의 나머지 부분을 이어서 tmp배열의 처음 칸부터 k번 인덱스까지 순차적으로 채워주면 된다.

시계 반대 방향으로 1번 회전시킨 것은 시계 방향으로 M-1번 회전시킨 것과 같고

마찬가지로 시계 반대 방향으로 2번 회전시킨 것은 시계 방향으로 M-2번 회전시킨 것과 같으므로

같은 함수를 이용해서 회전 횟수를M-k번으로 해주면 된다.

//인접한 숫자 중 같은 수 찾기

문제에 나와있는 인접한 수의 조건은 다음과 같다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

그냥 같은 원판(같은 행) 안에서 바로 양 옆이 인접한 수이고, 바로 위나 아래에 있는 원판 중에서는 같은 열이 인접한 수이다. 그래서 같은 원판 안에서는 마지막 숫자의 옆이 다시 첫 번째 숫자인 것을 처리해주어야 하지만

서로 다른 원판들의 위아래를 비교할 때는 맨 위의 원판과 맨 아래의 원판은 인접한 것이 아니므로 따로 처리해줄 필요는 없다.

//인접한 같은 수 지우기

또, 인접한 같은 수를 미리 지워서 0으로 만들어버리면 다른 방향으로 인접한 수와 비교할 수 없으므로 나중에 한 번에 지워줘야 한다. 그러기 위해서 인접한 같은 수를 가진 좌표들을 저장해놓아야 한다.

중복되는 좌표도 발생할 것 같아서 set을 이용하였다. 인접한 수를 찾으면 set에 원판의 위치(i, j)를 pair로 넣어주고, 나중에 set에서 한 번에 위치를 꺼내서 원판의 해당 위치의 숫자를 지워준다. 

(이때 나는 한쪽 방향으로만 비교하도록 구현했기 때문에 인접한 같은 두 수의 위치를 모두 넣어줬다)

//평균 구해서 더하고 빼주기

위에서 인접한 같은 수가 없어서 지워진 수가 하나도 없다면 문제 조건에 따라

원판에 있는 수들의 평균을 구해서(지워진 수는 제외) 평균보다 높다면 1을 빼주고 평균보다 낮다면 1을 더해준다.

c++에서 int형으로 몫을 구했다면 소수점을 제외한 몫만 저장하므로 나누어 떨어지지 않는 경우를 따로 처리해준다.

나누어 떨어지는 경우는 정말 값이 같은 경우이므로 값을 바꿔줄 필요가 없고

나머지가 있다면 실제 값은 몫+나머지 이므로 원판의 값이 평균보다 더 작은 것이므로 1을 더해준다.

//최종 답

T번의 회전이 모두 끝나면 원판의 숫자를 모두 더해준 값이 정답이다.

개인적으로 실수한 부분들 메모...

1. 평균을 구하는 과정에서 0으로 나누는 경우가 발생하면 안 된다.
2. 문제 조건에서 평균보다 큰 경우와 작은 경우에 대해만 나와있으므로 같은 경우에는 값이 변하지 않는다.
3. n과 m을 또 반대로 씀... 문제에서 반대로 해놓은 것이 아니었음에도 불구하고...
4. 문제 조건을 제대로 안 읽고, 인접한 수가 없는 경우 평균을 구해서 값을 변경시켜주는 부분을 안봄...
5. 인접한 같은 수 두 개를 set에 넣을 때 하나만 넣어줘서 제대로 안 지워짐

https://www.acmicpc.net/problem/10757

수의 범위가 long long의 범위도 넘어가는 경우에는 문자열로 구현해주어야 한다.

이 문제를 풀어놓으면 활용해서 풀 수 있는 문제들이 꽤 있다. (1914 하노이탑, 2407 조합, 10826 피보나치 수 4 등)

15353번 큰 수 A + B (2) 문제는 아예 똑같은 코드로 풀 수 있다.

먼저 문자열 두 개를 입력받았으면 덧셈을 해주기 위해서 자릿수를 맞춰주어야 한다.

길이를 비교하고 길이가 더 짧은 곳에 0을 붙여준다.

예를 들어 123456과 123456789이라면 123456 앞에 두 수의 길이의 차이인 3만큼 0을 붙여줘서 000123456을 만들어준 후에 덧셈을 진행한다.

각각의 자리에서 더해주고 9보다 큰 값이 있다면 다음 자릿수의 덧셈에서 1을 더 더해준다.

이런 식으로 정답 문자열에 붙여주면 거꾸로 되므로 마지막에 문자열을 뒤집어준다.

https://www.acmicpc.net/problem/1331

1. 나이트의 이동 경로가 맞는지
2. 모든 칸을 정확히 한 번씩만 방문했는지
3. 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는지

모든 이동에서 위의 1번과 2번의 경우를 확인해주고 마지막 칸에서 3번 조건을 확인한다.

하나라도 조건에 맞지 않다면 Invalid를 출력하고 모든 조건을 만족한다면 Valid를 출력한다.

현재 좌표가 x, y 라고 할 때, 나이트가 이동할 수 있는 경로는 위의 그림과 같다.

즉, (x, y)와 이동할 좌표의 차이의 절댓값이

x가 1인 경우에 y는 2이고, x가 2인 경우에 y는 1이면 된다.

https://www.acmicpc.net/problem/4179

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력하는 BFS문제이다.

3055번 탈출 문제(문제 링크)랑 비슷한 것 같다.

탈출 문제에서는 물이 퍼지는 시간을 먼저 BFS로 저장해놓고, 고슴도치가 이동할 곳의 시간이 물이 퍼진시간보다 작은 경우에만 이동할 수 있도록 구현했다. (문제 풀이 링크)

이번에도 똑같이 풀어봤는데 정답은 뜨지만 메모리를 많이 써서 다른 방법으로 다시 풀어봤다.

먼저 지훈이가 이동할 좌표와 불이 확산될 좌표를 각각 다른 큐에 넣어놓고 이동시킨다.

그리고 매분마다 불을 먼저 이동시키고 지훈이를 이동시키면 불이 확산되지 않은 곳으로 이동할 수 있다.

(입력받을 때 지훈이의 위치는 지나갈 수 있는 공간이므로 '.'으로 바꿔줘야 한다.)

미로를 탈출하는 경우는 입력으로 주어지는 지도 밖으로 벗어나는 경우이므로

배열의 크기를 더 크게 잡아서 범위를 벗어나는 경우에 탈출한 것으로 본다.

아래 그림처럼 지도를 (1, 1)부터 입력받으면 지훈이의 위치가 0행이거나 0열이거나 R+1행이거나 C+1 열인 경우 미로를 탈출한다.

BFS를 진행할 때에는, 먼저 지훈이가 이동할 수 있는 곳이 더 없다면 끝나기 때문에 지훈이의 좌표를 담은 큐가 비었다면 BFS를 종료한다. 그리고 매분마다 불을 먼저 확산시키고 다음에 지훈이를 이동시키기 위해서

각자의 큐사이즈만큼씩만 진행하면 된다.

한 번에 이동할 수 있는 위치만큼(현재 위치로부터 1만큼 이동한 곳)이 큐에 새로 들어가기 때문이다.

지훈이가 미로를 탈출했다면 그때의 시간을 출력하고 바로 리턴해서 종료시킨다.

이 부분에서 종료되지 않고 BFS탐색을 끝낸다면 탈출이 불가능한 경우이므로 IMPOSSIBLE을 출력하고 종료한다.

https://www.acmicpc.net/problem/1938

처음 주어진 통나무의 위치로부터 가능한 동작(U, D, R, L, T)을 모두 사용하여 도착지점까지 이동하면 된다.

이동할 때마다 매번 U, D, R, D, T를 해보고 이동이 가능하다면 동작수를 증가시켜서 이동하면 된다.

이동했을 때 범위를 벗어나거나 / 잘려지지 않은 나무가 있는 경우가 아니라면 이동 가능하다.

최소 동작수를 구해야 하므로 이미 갔던 좌표에도 다시 갈 필요가 없다.

하지만 통나무의 방향이 가로방향으로 온 것과 세로 방향으로 온 것은 구분해주어야 한다.

특히, 회전(T)을 할 때에는 3X3 정사각형 위치에 나무가 있거나 범위를 벗어나지 않는지 모두 확인해주어야 한다.

처음 입력받을 때 처음 통나무 위치의 좌표( pair<int, int> start[3] )와

이동할 위치의 좌표( pair<int, int> dest[3] )를 각각 배열에 저장한다.

그리고 실제 이동은 통나무의 길이는 3으로 정해져 있으므로 중심점의 좌표만 이용하여 이동한다.

처음 방향은 이어진 두 좌표가 같은 x좌표라면 (같은 행에 있다면) 가로 방향이고

그렇지 않다면(다른 x좌표 == 다른 행) 세로 방향이다.

이 중심점의 좌표와 방향을 이용하여 통나무를 이동시킨다.

이동할 통나무의 정보는 Tree라는 구조체를 만들어서 저장하였다.

Tree는 x좌표와 y좌표 dir(방향), cnt(동작수)를 가지고 있다.

방향은 0이면 가로방향 1이면 세로 방향으로 해놓았다.

이동이 가능할 때마다 이동할 중심 좌표의 위치와, 방향, 이전 동작수 +1을 해서 새로 큐에 넣어주면 된다.

최소 동작 수로 이동시키기 위해서 BFS를 사용하는데

방향이 가로방향인지 세로 방향인지에 따라 이동할 위치를 검사할 조건이 다르므로 각각 구현해준다.

이동한 위치의 중심 좌표가 목표한 지점의 중심 좌표와 같고 방향도 같다면 목표지점에 도착한 것이므로 그때의 동작수가 정답이다.

https://www.acmicpc.net/problem/17780

17837번 새로운 게임 2 문제(문제 링크)와 거의 똑같은데 조금 더 쉬운 시뮬레이션 문제이다.

(문제 풀이 링크)

이 문제에서는 말이 맨 밑에 있지 않으면 이동시킬 수 없다는 것이 17837번 문제와의 차이점이다.

말의 정보는 구조체를 만들어서 행과 열의 위치, 방향을 넣어서 벡터에 저장한다.

벡터의 i번째 위치에는 i번째 말의 위치와 방향이 저장되어 있다.

방향 정보는 문제에서 알려준 순서대로 오른쪽, 왼쪽, 위쪽, 아래쪽이 각각 1, 2, 3, 4번의 인덱스가 되도록 배열에 넣어놓는다. 1번부터 시작하기 위해서 0번 위치에는 그냥 0을 넣어놨다.

말을 이동시키기 위해서는 deque배열을 사용하였다.

deque<int> dq[13][13];

위와 같이 deque<int>를 타입으로 가지는 2차원 배열이다.

dp[x][y]에는 x행 y열 위치에 있는 말들이 순서대로 저장되어 있다.

이제 턴을 진행하면서 4개 이상이 쌓이는 경우가 있다면 바로 게임을 종료하고 턴 수를 리턴한다.

문제 조건에 따라 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력하기 위해서 -1을 리턴한다.

각 턴에서는 1번 말부터 k번말까지 순차적으로 이동시킨다.

문제 조건에 따라 이동시키기 전에 현재 이동시킬 말이 맨 밑에 있지 않다면 이동할 수 없으므로 바로 리턴한다.

이동시킬 말이 맨 밑에 있다면 이동할 칸의 색깔에 따라서 이동하게 된다.

이동할 칸이

1. 범위를 벗어나거나 파란색 칸인 경우
   • 원래 좌표에서 방향을 반대로 바꾼다.
     1. 다시 한 칸을 이동할 건데 이동할 칸이 또 범위를 벗어나거나 파란색일 경우 문제 조건에 따라 방향만 바꾼 채로 더 이동하지 않는다.
     2. 그렇지 않다면 이동을 한 건데 이동할 칸이 흰색이냐 빨간색이냐에 따라 다르게 이동할 것이므로 아래 조건들(밑에 2번, 3번 조건)을 이어서 실행해주면 된다.
2.  흰색인 경우
   • 현재 위치에 있는 말들을 순서대로 (큐의 앞부분부터) 이동할 위치로 이동시킨다.
3. 빨간색인 경우
   • 현재 위치에 있는 말들을 반대 순서로(큐의 뒷부분부터) 이동할 위치로 이동시킨다.

이동을 매번 할 때마다이동한 칸에 쌓인 말이 4개 이상이 되었는지 확인하고

4개 이상이 되었다면 true를 리턴, 그렇지 않다면 false를 리턴한다.

https://www.acmicpc.net/problem/17837

시뮬레이션 문제이다. 어떻게 말의 정보들을 저장하고 말을 이동시킬까 고민하다가 다음과 같이 구현해봤다.

말의 정보는 구조체를 만들어서 행과 열의 위치, 방향을 넣어서 벡터에 저장한다.

벡터의 i번째 위치에는 i번째 말의 위치와 방향이 저장되어 있다.

방향 정보는 문제에서 알려준 순서대로 오른쪽, 왼쪽, 위쪽, 아래쪽이 각각 1, 2, 3, 4번의 인덱스가 되도록 배열에 넣어놓는다. 1번부터 시작하기 위해서 0번 위치에는 그냥 0을 넣어놨다.

말을 이동시키기 위해서는 deque배열을 사용하였다.

deque<int> dq[13][13];

위와같이 deque<int>를 타입으로 가지는 2차원 배열이다.

dp[x][y]에는 x행 y열 위치에 있는 말들이 순서대로 저장되어 있다.

(queue가 아닌 deque를 사용한 이유는 이동할 칸이 빨간색인경우 순서를 반대로 넣어주기 위해서 사용하였다.)

(효율적인 방법인지는 잘모르겠다. 채점현황을 보니 메모리를 더 사용하는 것 같은데 다른 분들 풀이도 찾아봐야겠다...)

이제 턴을 진행하면서 4개 이상이 쌓이는 경우가 있다면 바로 게임을 종료하고 턴 수를 리턴한다.

문제 조건에 따라 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력하기 위해서 -1을 리턴한다.

각 턴에서는 1번말부터 k번말까지 순차적으로 이동시킨다.

이동할 칸이

1. 범위를 벗어나거나 파란색 칸인 경우
   • 원래 좌표에서 방향을 반대로 바꾼다.
     1. 다시 한칸을 이동할건데 이동할 칸이 또 범위를 벗어나거나 파란색일 경우 문제 조건에 따라 방향만 바꾼채로 더 이동하지 않는다.
     2. 그렇지 않다면 이동을 한건데 이동할 칸이 흰색이냐 빨간색이냐에 따라 다르게 이동할 것이므로 아래 조건들(밑에 2번, 3번 조건)을 이어서 실행해주면 된다.
2.  흰색인 경우
   • 현재 이동할 말의 번호가 num이라고 했을때
   • 현재 이동할 말의 위에 있는 말들을 함께 이동시켜주기위해서 deque에서 num번 말이 나오는 이후의 말들은 모두 같이 이동시켜주면된다.
   • deque에 들어있는 말들의 개수만큼만 반복문을 진행하면서
     1. num번이 나오지 않았다면 다시 원래 위치 deque에 넣어준다.
     2. num번이 나왔거나 이전에 num번이 나왔다면 이동할 위치의 deque에 넣어준다. (이동할 때는 해당 말의 위치정보(벡터에 넣어놓은 값)을 업데이트 해주어야한다)
3. 빨간색인 경우
   • 현재 이동할 말의 번호가 num이라고 했을때
   • 현재 이동할 말의 위에 있는 말들을 순서를 반대로 이동시켜주기 위해서 deque의 뒷부분부터 num번까지의 말들을 순차적으로 이동시켜준다.
   • deque에 들어있는 말들의 개수만큼만 반복문을 진행하면서 num이 나올때까지 이동할 위치의 deque에 넣어주고 num번이 나온다면 num번말도 이동시켜주고 반복문을 종료한다.

이동을 매번 할때마다 이동한 칸에 쌓인 말이 4개 이상이 되었는지 확인하고

4개 이상이 되었다면 true를 리턴, 그렇지 않다면 false를 리턴한다.

https://www.acmicpc.net/problem/1600

최소 동작수를 구하는 문제이므로 bfs로 이동할 수 있는 방법을 매번 사용하여 정답을 구하면 된다.

벽 부수고 이동하기 문제와 비슷하게 풀었다.

인접한 네 방향으로 이동하는 경우와 아직 능력을 k번만큼 사용하지 않았다면 말의 움직임처럼 이동하는 경우를 모두 큐에 넣어주고 이동할 때마다 배열에 동작 수를 저장한다.

이때 해당칸에 도착할 때 능력을 몇 번 사용했는지에 따라 다르므로 삼차원 배열을 사용한다.

visit[x][y][z] = (x, y) 좌표에 능력을 z번 사용해서 온 동작의 수

마지막 visit[h-1][w-1][0]부터 visit[h-1][w-1][k]까지 중 최솟값이 정답이다.

(마지막 칸에 도착했을때 능력을 0번 사용한 경우부터 k번 사용한 경우 중 최솟값)