알고리즘매일매일

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

각 칸은 방향이 정해져 있기 때문에 하나의 방향으로만 이동하여 경로는 정해져 있게 된다. 즉 탈출하는 경로를 찾으면 해당 경로에 해당하는 칸들은 모두 탈출 가능하다. 마찬가지로 탈출할 수 없는 경로가 있다면 해당 칸들은 모두 탈출 불가능하다. 참고로 경로를 따로 저장해놨다가 나중에 다시 한번에 체크해주는 방식으로 구현하면 시간 초과가 발생하므로 DFS로 구현해야 한다.

3 3

DDR

DLU

LLL

문제의 2번째 예제로 예를 들어보면 첫 번째 칸(0, 0)인 D에서 출발하면 정해진 방향에 따라 D-D-L의 경로로 탈출이 가능하다. 그러면 당연히 (1, 0)인 D에서도 D-L 로도 탈출 가능하고, (2, 0) L에서도 탈출 가능하다. 정확히는 L에서 탈출이 가능한 것이고 위의 D에서는 L로 향하게 방향이 되어있기 때문에 마찬가지로 탈출이 가능하다.

3 3

DDR

DLU

LLL

다음에 (0, 1) 칸인 위의 파란색 D에서 출발하면 아래로 내려와 L에 도착하고 L에서는 (1, 0)인 D에 도착한다. 그러면 위에서 이미 탈출 가능하다고 확인되었으므로 D에서 L까지 오는 경로는 모두 탈출 가능하다고 판단이 가능하다.

3 4

RRDD

RRDR

DULU

문제의 예제 입력 4번을 마지막 예시로 들어보면 처음 (0, 0)인 R에서 출발했을 때, R-R-D-D-L-U-R까지 왔다가 다시 D로 와서 사이클이 발생하기 때문에 탈출이 불가능하다. 이때의 각 경로에서는 탈출이 불가능하다는 것을 저장해놓으면 다음 (0,1), (0,2) 등의 빨간 경로에서는 다시 탐색할 필요가 없다.

3 4

RRDD

RRDR

DULU

마찬가지로 (1, 0)에서 출발하면 미리 저장해놓은 탈출할 수 없는 경로인 (1, 1) R에 도착하므로 탈출할 수 없는 칸이라는 것을 금방 알 수 있다.

이제 구현을 위해서는 문자를 입력받을 map배열 이외에 두 가지 배열을 더 사용하였다.

x, y 칸에서 탈출이 가능한지 저장할 check배열과 매번 각 탐색에서 방문했는지 확인할 visit배열을 사용하였다.

check배열의 값이 1이면 탈출 가능 / 2이면 탈출 불가능 / 0이면 아직 확인 안 됨으로 해놓고 구현했다.

또한, 이동한 경로를 저장하기 위해서 DFS를 사용하였다. 이동할 수 있는 칸까지 계속 이동하다가 탈출에 성공하거나 사이클이 발견돼서 실패하는 칸을 발견할 때까지 쭉쭉 탐색을 한다. 탈출에 성공했다면 true값을 리턴하고 실패했다면 false값을 리턴한다. DFS로 리턴 받은 값이 true이면 현재 칸에서 탈출이 가능하다는 뜻이므로 check배열 값을 1로 바꿔주고 탐색에서 돌아왔으므로 visit배열은 false로 바꿔준다. 반대로 false를 리턴 받았다면 check배열의 값을 2로 해주고 visit배열은 마찬가지로 false로 바꿔준다.

다시 정리를 해보면 복잡해 보이긴 하지만 아래와 같다.

1. 입력을 받는다.
2. 모든 칸을 검사하여 탈출할 수 있는지 검사한다.
   • 이미 탈출 불가능한 칸으로 확인되었다면 DFS탐색을 하지 않고 다음 칸으로 넘어간다.
   • 이미 탈출 가능한 칸으로 확인되었다면 정답 카운트를 증가시키고 DFS탐색을 하지 않는다. 마찬가지로 다음 칸으로 넘어간다.
   • 확인되지 않은 칸이라면 DFS로 이동해서 경로를 확인하고 탈출할 수 있다면 정답 카운트를 증가시킨다.
3. 탈출할 수 있는지 검사하기 위해 DFS를 진행한다.
   •  해당 칸에 적혀 있는 문자에 따라 좌표를 이동한다.
   • 범위를 벗어나면 탈출에 성공한 것이므로 해당 좌표의 check배열 값을 1로 바꿔주고 true를 리턴한다.
   • 방문한 칸의 check배열을 값이 1이라면 이미 탈출 가능한 칸이라고 확인됐으므로 check배열의 값을 1로 바꾸고 true를 리턴한다.
   • visit배열을 확인하여 이번 탐색에서 방문했던 칸을 다시 방문하거나(cycle 발생) check배열을 확인했을 때 값이 2로 이미 탈출 불가능한 칸이라고 확인됐으면 check배열의 값을 2로 해주고 false를 리턴한다.
   • 위의 경우들이 아닌 이동한 칸에서 이동을 계속하는 경우에는 DFS탐색을 계속해주면 된다. visit배열을 true값으로 바꿔놓고 재귀 호출로 다음 칸으로 이동한고, 재귀 호출에서 돌아오면 visit배열을 다시 false값으로 바꿔준다. 탐색 결과에 따라 check배열의 값을 바꿔주면 되는데, 결과는 위의 3가지 상황 중에서 true나 false를 리턴 받은 값이다. 이전의 호출 함수에게도 이 결과를 그대로 리턴해줘서 현재 경로의 해당하는 모든 칸에 탈출이 가능한지 체크하도록 해준다.

DFS의 기본 개념을 알고 있다면 어렵지 않은 문제다.

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

이분 탐색으로 조카들에게 나눠줄 수 있는 과자의 최대 길이를 찾아줘야 한다.

이분 탐색의 처음 범위는 1개를 나눠줄 수 있는 경우부터 가지고 있는 과자 중 가장 큰 과자의 길이까지가 된다.

3 10

1 2 3 4 5 6 7 8 9 10

문제의 첫 번째 예시처럼 다음과 위와 같이 막대과자를 가지고 있다면 1에서 10까지의 범위를 탐색해준다.

4 3

10 10 15

2번째 예제에서의 범위는 1부터 15까지이다.

문제의 예시에서는 막대과자의 길이가 모두 정렬된 순서로 되어있지만 히든 케이스에서는 정렬되어 있지 않을 수도 있으므로 입력받은 막대과자의 길이 배열을 정렬해놓고 탐색을 시작한다.

이분 탐색으로 매번 mid값을 구해서 mid길이만큼을 조카들에게 나눠줄 수 있는지 검사한다.

나눠줄 수 있다면 더 큰 길이로 나눠줄 수 있는지 mid값보다 큰 범위를 탐색하고, 나눠줄 수 없다면 더 작은 길이를 찾아야 한다.

나눠줄 수 있는지 검사할 때에는 길이가 긴 막대과자들부터 mid길이만큼을 나눌 수 있는지 확인한다. 배열을 앞에서 정렬해놓았으므로 배열의 뒤쪽부터 검사해주면 된다. mid길이만큼의 막대과자가 조카의 수이상 나온다면 mid 길이만큼씩 나누어줄 수 있다.

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

이 문제의 정답률이 낮은 것은 방향이 헷갈려서인 것 같다. 우선 1번 인덱스가 왼쪽 아래부터 시작하고, 입력받는 x, y 도 반대이다. 문제에서 주어지는 아래 그림에서 오른쪽 위에 있는 로봇의 좌표는 (5, 4)인 것에 주의해야 한다.

위의 그림을 아래 그림처럼 시계방향으로 90도 돌려서 생각하면 쉽게 풀 수 있다. (x <= A, y <= B)

일반적으로 사용하는 2차원 배열의 모양이므로 (x, y)를 입력받은 그대로 사용할 수 있다.

대신에 방향도 같이 90도 돌려야 하므로 W면 N방향으로/ N이면 E방향으로/ E면 S방향으로/ S면 W방향으로 바꿔준다.

로봇 정보는 현재 위치정보와 방향 정보를 구조체에 넣어서 관리한다. 로봇들은 처음에 입력받은 순서대로 번호를 가지므로 로봇 정보를 가지는 구조체를 벡터에 순차적으로 넣어놓는다. 벡터의 i번 인덱스 위치에 들어있는 로봇 정보가 i번 로봇의 정보이다. 1번 로봇부터 사용하기 위해 벡터에 0번 인덱스 위치에 아무 값을 넣어주고 시작하였다.

로봇이 이동하는 위치에 다른 로봇에 이미 있는지 검사하기 위해 2차원 int 배열에 로봇의 번호를 저장해놓는다.

배열의 (x, y)에 있는 로봇의 번호를 저장하고, 로봇이 없다면 초기값인 0이다.

예를 들어 로봇 2번이 (5, 4)에 있다면  check[5][4] = 2 이다.

이동후에는 기존 위치의 값을 다시 0으로 만들어주고 새로 이동한 곳에 로봇 번호를 다시 저장한다.

이후에는 입력받은 로봇 번호, 명령, 반복 횟수를 이용하여 시뮬레이션해주면 된다. 벽에 부딪히거나 다른 로봇에 부딪히는 경우는 F명령으로 이동했을 때만 발생하므로 F명령일 때만 검사해주면 된다.

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

처음에 무너질 모래성을 매번 검사해서 없애주는 방식으로 구현했다가 시간 초과가 났다.

어차피 나중에 무너질 모래성들은 이전에 무너진 모래성들이 없어져서 영향을 받으므로 무너지는 모래성의 위치로부터

주변을 탐색하여 또 무너질 모래성이 있는지 찾아주고 다시 없애주는 방식으로 구현하면 문제를 해결할 수 있다.

1. 입력을 받는다.
2. 입력 받은 배열에서 튼튼함이 9보다 작은 모든 모래성을 검사하여 자기 격자 주변의 8방향에 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 무너질 것이므로 큐에 넣어주고 배열에도 방문 표시를 해준다. 이때 다음에 무너져야 하는 모래성이 영향을 받으므로 바로 ' . '으로 바꿔주면 안 된다.
3. 파도가 한 번 칠 때의 무너질 모래성들을 모두 큐에 넣었다면, ' . '으로 바꿔준다. 그리고 무너질 모래성 주변의 8방향을 다시 검사하여 또 무너질 모래성이 있다면 큐에 넣어준다. 이때 기존에 큐에 들어가 있던 모래성의 개수(큐 사이즈)만큼만 탐색을 진행하여, 탐색이 끝난다면 파도치는 횟수를 증가시킨다.
4. 더 이상 무너질 모래성이 없어서 탐색이 끝난다면 파도치는 횟수를 출력하고 종료한다.

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

테이블의 행을 i-1번째까지 지운 상태에서 i번째행부터의 문자열을 검사한다고 했을 때, 동일한 문자열이 있다면 그 이후 문자열들도 중복이다. 예를 들어, abc와 abc가 중복이면 이후인 bc와 bc, c와 c가 중복이기 때문이다.

반대로 중복이 아니라면 i-1번째 행까지 지웠을 때에도 중복이 아니다. 그 이전에 중복이면 위와 같은 이유로 현재도 중복일 것이기 때문이다. 

이분 탐색으로 mid번째 행부터 시작하는 문자열(mid-1번째까지는 지워진 상태)을 검사하여 동일한 문자열이 발생한다면 mid 이전의 행을 탐색하고, 만약 동일한 문자열이 발생하지 않는다면 더 큰 값을 찾기 위해 mid이후의 행을 지웠을 때의 문자열들을 검사해서 정답을 구할 수 있다. 중복이 발생하지 않은 행 중 최댓값이 count값으로 정답이 된다.

문자열의 중복을 검사할 때에는 set을 이용하였다.

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

4179번 불! (문제 링크) 문제와 스토리가 비슷한 문제인 것 같다.  (4179 불! 풀이 링크)

이 문제는 테스트 케이스가 최대 100개로 여러 개 있기 때문에 매번의 테스트 케이스에서 배열과, 큐 등 초기화를 잘해주어야 한다.

상근이가 최단 시간으로 탈출하는 경우와 불이 퍼지는 것을 구현하기 위해 BFS를 사용한다.

BFS는 상근이가 이동할 수 있는 곳이 더 없다면 끝나기 때문에 상근이의 좌표를 담은 큐가 비었다면 종료한다.

또는, 탈출에 성공한 경우에 바로 탐색을 종료한다.

큐 2개를 사용하여 상근이와 불의 위치를 각각의 큐에 넣어주고 각각 BFS를 진행한다. 같은 시간 동안 불을 먼저 이동시키고 상근이를 이동시키면 불이 확산되지 않은 곳으로 이동할 수 있다. 매 초마다 불을 먼저 확산시키고 다음에 상근이를 이동시키기 위해서 각자의 큐 사이즈만큼씩만 진행하면 된다. 한 번에 이동할 수 있는 위치만큼(현재 위치로부터 1만큼 이동한 곳)이 큐에 새로 들어가기 때문이다.

상근이가 빌딩 지도 범위를 넘어가면 탈출에 성공한 것이므로 바로 true를 리턴하여 시간을 출력해준다.

BFS가 끝났는데 빌딩을 탈출하지 못했다면 false를 리턴하고 문제 조건에 따라 IMPOSSIBLE을 출력한다.

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

백준에서 BaaaaaaaaaaarkingDog님이 코딩 테스트 대비 모의고사로 출제하신 완전 탐색+bfs문제이다.

대회가 열렸을 때 들어가서 풀어봤는데 재밌었다. 처음 제출했을때 시간초과가 나서 당황했는데 쓸데없는 작업을 줄여줬더니 통과했다

(꽃이 피는 곳을 저장해놓은 배열을 나중에 처음부터 끝까지 확인해서 꽃의 수를 세줬었는데, 꽃이 필때 꽃을 바로 세는 걸로 바꿔줬다)

다른 한 문제는 18808 스티커 붙이기(문제 링크)이다. (18808 스티커 붙이기 풀이 링크)

풀이 코드는  BaaaaaaaaaaarkingDog님의 블로그에서도 볼 수 있다.

나는 다음과 같은 방법으로 풀었다.

1. 정원의 정보를 입력받을 때, 값이 2 (배양액을 뿌릴 수 있는 땅)이면 벡터에 넣어놓는다.
2. 앞에서 저장해논 배양액을 뿌릴 수 있는 땅들에 대해 배양액을 뿌리지 않는 경우 / 초록색 배양액을 뿌리는 경우 / 빨간색 배양액을 뿌리는 경우를 모두 골라준다. 배양액을 뿌리는 경우에는 뿌리는 배양액의 수 - 1을 매개변수로 넘기고 뿌리지 않는 경우는 배양액의 수를 그대로 넘긴다.
   • 이때 백트랙킹으로 시간을 줄여줘야 하므로
   • 남은 배양액의 수가 남아있는 배양액을 뿌릴 수 있는 땅보다 많으면 안 되므로 더 이상 탐색을 진행하지 않는다.(배양액을 남김없이 사용해야 하고, 땅에 배양액 2개를 사용할 수 없으므로)
   • 초록색과 빨간색 배양액을 둘 다 모두 사용했다면 남은 땅의 경우의 수를 더 정해주지 않고 바로 bfs로 배양액을 퍼뜨려준다.
3. bfs를 진행할 때에는 초록색 배양액과 빨간색 배양액을 각각 큐에 넣어서 따로 bfs를 진행해주는데, 도착한 시간을 저장하는 배열도 각각 사용한다. 또한, 각각의 큐 사이즈만큼씩 진행해서 bfs를 단계별로 진행한다.(각 초마다 bfs를 진행 가능)
   • 나는 먼저 초록색 배양액을 퍼뜨려줬다. 꽃이 피었거나 / 호수이거나 / 이미 배양액이 뿌려져 있는 경우를 제외하고 바로 퍼뜨리면 된다.
   • 그다음에 큐 사이즈만큼 진행함으로써 초록색 배양액을 뿌린 같은 시간 동안 빨간색 배양액을 뿌릴 수 있다. 빨간색 배양액을 뿌릴 때에는 초록색 배양액이 이미 뿌려져 있어도 같은 시간에 뿌려진 것이라면 꽃이 피므로 이때 꽃의 수를 늘려준다. 이때, 큐에는 넣지 않고 시간만 저장해줘서 다음에 배양액이 퍼지지 않도록 한다.
4. 배양액을 모두 퍼뜨렸다면 꽃의 수를 저장해놓은 최댓값과 비교한다.

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

백준에서 BaaaaaaaaaaarkingDog님이 코딩 테스트 대비 모의고사로 출제하신 시뮬레이션 문제이다. 대회가 열렸을 때 들어가서 풀어봤는데 재밌었다. 총 두 문제였는데 나머지 한 문제는 18809번 Gaaaaaaaaaarden (문제 링크)이다. (풀이 링크)

스티커 붙이기 문제가 좀 더 쉽다. 

먼저 매번

 sticker를 저장할 int배열 / 모니터에 스티커가 붙여졌는지 확인할 bool 배열 / 스티커를 90도 회전시킬 때 임시로 사용할 int 배열

이렇게 세 가지 배열을 사용하였다.

문제에서 나와있는 스티커를 붙이는 조건은 다음과 같다.

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

위의 조건에 따라 먼저 입력받은 스티커를 노트북의 위쪽부터 붙일 수 있는지 확인한다. 

(0, 0)부터 (N-R, M-C) 칸까지 각 칸을 스티커의 시작점으로 했을 때의 스티커를 붙이는 경우를 순차적으로 해보고

붙일 수 있다면 바로 그 자리에 붙인다. 문제 조건에서 스티커를 붙일 우선순위는 가장 먼저 가장 위쪽, 그다음에 가장 왼쪽이므로 일반적인 for문으로 돌리고 찾는 순간 바로 탐색을 종료하면 자연스럽게 구현할 수 있다.

스티커를 붙일 수 있는지는 단순히 스티커를 저장해놓은 배열과 모니터에 스티커가 붙어있는지 확인할 배열을 비교해주면 된다.

비교할 때나 모니터에 스티커를 붙여줄 때, 확인할 모니터의 시작점을 주의해야 한다.

스티커는 매번 (0, 0)부터 검사해주면 되지만 모니터는 스티커를 붙이기 시작하는 칸부터 검사해야 하므로

스티커를 모니터의 (x, y) 칸부터 붙여본다고 한다면 스티커의 (i, j)를 확인할 때는 모니터의(i+x, j+y) 칸을 비교해주어야 한다.

모니터에 이미 스티커가 있는데 모눈종이 위에도 스티커가 있다면 붙일 수 없으므로 바로 false를 리턴해서 다음 경우로 넘어간다.

붙일 수 있다면 모니터에 스티커를 붙여주고 다음 스티커로 넘어간다.

모든 칸에서 시작해도 스티커를 붙일 수 없다면 90도 회전해서 똑같은 과정을 반복한다.

90도씩 회전시켜서 모든 경우(0도, 90도, 180도, 270도)를 해봤는데도 붙일 수 없다면 문제 조건에 따라 해당 스티커는 버린다.

90도 회전을 시킬 때는 위의 그림과 같이 tmp배열의 index를 기준으로 복사해줬다.

90도 회전하게 되면 행의 수(R)와 열의 수(C)가 되므로 for문에서 i는 C 전까지, j는 R 전까지 해주면 된다.

for문을 이용해서 tmp배열은 순차적으로 채워주면 되고, 스티커 배열은 i와 추가적인 변수 l 을 사용해서 위의 그림에 나와있는 순서대로 값이 들어가도록 구현했다. 코드로 보면 다음과 같다.

for (int i = 0; i < c; i++) {

        for (int j = 0, l = r-1; j < r; j++, l--) {

            tmparr[i][j] = sticker[l][i];

        }

    }

tmp배열에 모두 복사했다면 R과 C의 값을 아예 바꿔주고 tmp배열의 값을 원래 스티커 배열로 다시 옮겨준다.

k번의 스티커를 모두 붙여 본 후에 모니터에 스티커가 붙여져 있는지 확인하는 배열을 검사해서 최종 답을 구한다.