버러범의 개발이야기

BOJ 문제 링크 : https://www.acmicpc.net/problem/2580

스도쿠는 아래와 같은 규칙으로 빈칸을 채워나가는 게임이다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

2. 굵은 선으로 구분되어 있는 3*3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

입력될때 빈칸은 0으로 입력된다.

입력으로 스도쿠 문제가 주어졌을때 알맞게 빈칸을 채운 9*9 행렬을 출력하는 문제이다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%232580.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크 : https://www.acmicpc.net/problem/1987

R * C 크기의 표 모양의 보드가 알파벳으로 이뤄진채 주어진다.

말은 보드의 좌측 상단에서 시작해 상하좌우 4방향으로 한 칸씩 이동 가능하다.

단, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과 달라야한다.

이때 말이 최대한 몇칸을 지날 수 있는지 구하는것이 문제이다.

해당 문제는 dfs를 이용하여 문제를 풀 수 있다.

여기서 중요한점은 이미 지나온 경로에 있는 알파벳을 따로 저장하여 앞으로의 경로와 비교해야 한다는 것이다.

나는 지나온 알파벳을 비트마스크 형태로 저장하여 다음 경로의 알파벳과 bit단위 비교를 하여 다음 경로가 유효한지 판단하였다.

코드 원본 : https://github.com/sbl133/BOJ/blob/main/%231987.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크 : https://www.acmicpc.net/problem/1011

출발점에서 도착점까지 이동장치를 이용하여 이동한다 했을때 이동 규칙은 다음과 같다.

바로 직전 이동거리가 k광년이면 이번에 이동 가능한 거리는 k-1, k, k+1 셋 중 하나이다.

음수 혹은 0거리만큼의 이동은 의미가 없다(이동 불가능 하다).

이러한 규칙으로 이동한다 했을때 공간이동 장치 작동 횟수의 최소값을 구하는 문제이다.

이러한 종류의 문제는 일단 가까운 거리부터 어떤방식으로 이동해야 가장 빨리 갈 수 있는지를 나열해 보면된다.

나열하다 보니깐 다음과 같은 규칙을 찾을 수 있었다.

작동 장치를 1번 쓰는 경우 갈 수 있는 거리 : 1(1) - 1개

작동 장치를 2번 쓰는 경우 갈 수 있는 거리 : 2(11) - 1개

작동 장치를 3번 쓰는 경우 갈 수 있는 거리 : 3(111), 4(121) - 2개

작동 장치를 4번 쓰는 경우 갈 수 있는 거리 : 5(1211), 6(1221) - 2개

작동 장치를 5번 쓰는 경우 갈 수 있는 거리 : 7(12211), 8(12221), 9(12321) - 3개

작동 장치를 5번 쓰는 경우 갈 수 있는 거리 : 10, 11, 12 - 3개

작동 장치를 6번 쓰는 경우 갈 수 있는 거리 : 13, 14, 15, 16 - 4개

작동 장치를 7번 쓰는 경우 갈 수 있는 거리 : 4개

작동 장치를 8번 쓰는 경우 갈 수 있는 거리 : 5개

.

.

.

장치를 2번씩 더 쓸때마다 갈 수 있는 거리가 1개씩 더 늘어나는것을 알 수 있었다.

이러한 규칙을 토대로 프로그래밍을 하면 다음과 같다.

코드 원본 : https://github.com/sbl133/BOJ/blob/main/%231101.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크 : https://www.acmicpc.net/problem/2206

N * M 크기의 맵이 있다. 맵에서 벽은 1, 벽이 없는 곳은 0으로 표현된다.

(1,1)에서 (N,M) 위치까지 상하좌우로 한칸씩 이동면서 최단경로를 구하는 문제이다.

이때 벽을 부수고 이동하는 경우 경로가 더 짧아진다면, 벽을 한 개 까지 부수고 이동하여 된다.

bfs를 이용하면 문제를 해결할 수 있다. 이때 이미 지나온 곳을 다시 지나는것을 막기위해 discover배열을 둔다.

단, 벽을 부술 수 있는 상태인지 이미 벽을 부순 상태인지에 따라 이동할 수 있는 경로가 달라지므로 discover를 이차원이 아닌 3차원 배열로 한다.

코드원본: https://github.com/sbl133/BOJ/blob/main/%232206.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

BOJ 문제 링크: https://www.acmicpc.net/problem/7576

N * M 크기의 배열 형태로 격자모양을 한 토마토 상자의 정보가 주어진다. 각 칸에는 0, 1, -1이 올 수있는데 각각 익지않은 토마토, 익은 토마토, 빈칸을 의미한다.

익은 토마토는 앞, 뒤, 좌, 우 4방향으로 익지 않은 토마토에게 영향을줘 다음날 익게만든다.

이러한 조건 속에서 토마토들의 정보가 주어졌을때 며칠이 지나면 토마토들이 모두 익는지 그 최소 일수를 구하면 되는 문제이다.

단, 토마토들이 전부 익는 경우가 없으면 -1를 출력한다.

bfs를 이용하면 문제를 풀 수 있지만 날짜를 계산하기 위해서는 추가적인 로직이 필요하다.

이를 위해서 앞으로 익을 토마토들의 목록을 저장하는 queue에 날짜구분자를 삽입하여 날짜를 구분할 수 있도록 한다.

코드 원본: https://github.com/sbl133/BOJ/blob/main/%237576.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

알고스팟 문제 링크: https://algospot.com/judge/problem/read/TPATH

각 도시들을 잇는 철도망이 주어질 때, 0번 도시에서 출발해서 V-1번 도시에 도착하는 경로들 중 최대 운행 속도와 최소 운행 속도의 차를 최소화하는 경로를 찾는 문제이다.

0번 도시와 V-1번 도시가 연결될 때까지 하한을 높여가며 다음과 같은 동작을 반복한다.

하한을 두고 kruscal알고리즘을 이용하여 하한이상의 가중치를 가진 철도부터 가중치 순서대로 그래프에 추가한다.

이때 kruscal의 시간복잡도를 지배하는 것은 edges를 가중치의 오름차순으로 정렬하는 작업이다.

문제에서 철도의 가중치가 변하지는 않으므로 edges를 정렬하는 작업을 선행처리한 후 나머지 부분만 하한을 높여가며

반복하면 기존의 kruscal알고리즘을 edges.size번 반복하는 것보다 빠르게 문제를 해결 할 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/31.%20MST/TPATH.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/LAN

건물들의 위치가 2차원 좌표로 주어지고 현재 연결된 케이블들이 주어졌을때, 모든건물들을 연결하기 위한 최소 케이블 길이를 구하는 문제이다.

현재 연결되어있는 간선들의 길이가 0이라 하고 kruscal알고리즘을 이용하여 문제를 풀 수 있다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/31.%20MST/LAN.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2

알고스팟 문제 링크: https://algospot.com/judge/problem/read/PROMISES

도시를 연결하는 고속도로들이 있다. 추가적인 고속도로 건설 계획에서 입력순서대로 고속도로를 건설한다 했을때

고속도로 건설의 정당성은 기존에 고속도로를 통해 오갈 수 없던 두 도시가 새로 연결되거나, 두 도시를 오가는 데 걸리는 시간이 단축되는것, 둘 중 하나라도 만족해야 한다.

이때 정당성이 없는 고속도록 건설 계획의 개수를 구하는것이 문제이다.

경유할 수 있는 정점의 목록을 늘려가는 기존의 플로이드 알고리즘을 간선의 목록을 늘려가는 방식으로 변형하면 문제를 해결할 수 있다.

먼저 기존의 플로이드 알고리즘을 이용하여 이미 존재하는 고속도로들만을 이용한 최단경로를 계산한다.

그 후 입력 순서대로 건설 예정인 고속도로를 추가하는 앞에서 언급한 변형된 플로이드 알고리즘을 사용하여 최단거리 갱신 유무를 확인한 후 갱신 가능하다면 최단거리를 갱신한다.

이때 주의할점은 어느 방향으로 간선을 타고 갈 것인가를 정해야하기 때문에 정점을 추가할때와는 달리 경우의 수가 3개로 늘어난다.

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/PROMISES.cpp

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2