Diary

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

문제 이해

빌딩 공간이 주어지고, 해당 공간에는 벽과 문서, 문과 열쇠를 표현하는 문자들이 주어집니다. 최초에 가지고 있는 열쇠가 있으며 길을 가다가 열쇠를 주울 수도 있습니다. 열쇠를 가지고 있으면 해당 하는 열쇠에 맞는 문은 얼마든지 열 수 있습니다. 이러한 정보들이 주어졌을 때 가장 많이 주울 수 있는 문서의 갯수를 구하는 문제였습니다.

입출력 조건

시간초 제한은 1초였으며 빌딩의 크기는 최대 100x100 이었습니다. 테스트 케이스의 갯수는 100개까지였으며 bfs를 돌면 되겠다 생각했습니다.

풀이

1. 첫번째로 풀었던 방법은 가지고 있는 키를 map에 저장해 두고 외곽의 모든 정점에서 bfs를 돌며 bfs를 도는 것이였습니다. 그러다 키를 만나게 되면 해당 키를 보유한 키에 추가하고 다시 그지점에서 bfs를 돌았습니다. 이렇게 되면 구현도 복잡할 뿐더러 시간적으로도 비효율 적이였습니다. 100 * 100 * 100(테케) * 100이상(같은지점 반복횟수)

여기서 첫번째 팁을 얻었습니다.

팁은 키를 map에 유지하는 것이 아니라 키의 최대 갯수는 26개 이므로 visit배열에 키 보유에 관한 정보를 저장하는 것이였습니다.

이를 듣고 2^26의 범위를 확인해 보았고 비트마스킹을 활용하면 되겠구나 생각하였습니다.

2. 키의 정보를 visit 배열에 저장해 두고 bfs를 한번만 돌았습니다. visit배열에 있는 키가 같으면 그냥 넘겨주고 갱신이 된 경우에는 다시금 돌아주게 구현해 주었습니다.

여기서 두번째 팁을 얻었습니다.

저는 구현할 때 모든 외곽 지점을 확인하고 조건을 따져서 들어갈 수 있는 곳에서는 모두 bfs를 돌려주려고 하고 있었습니다. 이때 진짜 생각지도 못한 방법을 알려주었습니다. 외곽을 모두 빈공간으로 채우고, 즉 실제로 존재하는 범위 밖으로 빈공간을 둘러싸 주고 0,0 부터 bfs를 돌리면 되는 것이었습니다!! 이거 들었을 때 진짜 우와ㅏ...했습니다.. 이런방법이!!!

이렇게 하니 진짜 깔끔하게 코드가 작성되었습니다!

에러 및 느낀 점

비트 마스킹을 이용하는 것이 참신하고 재미있었습니다.

구현력이 아직 많이 부족하다는 생각도 들었고 앞으로 많이 풀면서 저도 이렇게 바로바로 생각나도록 하는 연습을 많이 해야겠습니다,,오늘도 많이 배워갑니다

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/9328_%EC%97%B4%EC%87%A0.cpp

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

문제 이해

0과 1로 구성되어있는 공간이 주어지고 1은 문자의 일부분을, 0은 빈공간을 뜻합니다. 여기서 상하좌우 뿐만 아니라 대각선으로 이어져 있는 것도 하나로 이어져 있는 것으로 취급하며 전체 몇글자로 이루어져 있는지를 알아보는 문제였습니다.

입출력 조건

현수막 크기는 250x250이 최대였으며 시간제한은 2초였습니다.

BFS를 이용하면 쉽게 풀 수 있다고 생각되었습니다.

풀이

단순히 bfs를 돌리는데 일반적인 상하좌우가 아니라 대각선까지 이동이 가능하도록 해주는게 포인트였던 것 같습니다.

또한 전체를 탐색하며 bfs를 돌리고, bfs를 돌린 횟수가 곧 문자의 갯수가 되었습니다.

에러 및 느낀 점

단순 구현력을 보는 문제였다고 생각됩니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/14716_%ED%98%84%EC%88%98%EB%A7%89.cpp

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

문제 이해

최대 20x20 크기의 방에 1x1 크기의 깨끗한 공간, 더러운 공간, 가구가 있는공간, 시작 위치가 있습니다. 시작위치에서 시작하여 더러운 곳을 모두 거쳐 방에서 더러운 곳이 없어지도록 하는 최소한의 경로가 몇인가를 묻는 문제였습니다. 이때 왔던 공간을 다시 지나갈 수 있었습니다. 만약 모든 곳을 깨끗하게 할 수 없다면 -1을 출력합니다.

입출력 조건

방의 최대 크기는 20x20 이며, 더러운 공간은 10칸 미만입니다.

시간 제한은 1초였습니다.

풀이

최대 9칸이 더러운 공간이므로 시작점에서 모든 더러운 공간으로 BFS를 시도하여 깨끗하게 할 수 있는지를 체크하였습니다.

처음에는 최단거리와 관련된 문제라고 생각하여 priority_queue를 이용하여 문제를 해결하려 하였으나 생각대로 작동하지 않았습니다. 그래서 결국 현재 위치와, 다른 더러운 점들을 방문하는게 목적이기 때문에 시작점과 다른 더러운 점들을 따로 정점으로 만들고, bfs로 두 정점 사이의 거리를 구하여 가중치로 이용하였습니다.

그렇게 새로운 그래프가 하나 생기게 되었고 이는 최대 10개의 정점을 가지므로 이는 완탐을 하여도 10!의 시간이 걸리게 됩니다.

이에 완탐을 통해 문제를 해결하였습니다.

1. 모두 깨끗하게 할 수 있는지부터 확인

2. 모두 깨끗하게 할 수 있다면 시작 점과 더러운 곳들을 새로운 하나의 정점으로 생각하고 사이의 거리를 가중치로 하는 새로운 그래프를 생성함

3. 새로운 그래프는 정점의 최대 갯수가 10개이므로 완전탐색으로 풀어도 시간초과가 나지 않음

전체코드는 아래를 참고해 주세요

에러 및 느낀 점

생각했던 방법은 반은 맞고 반은 틀렸던거 같아 뿌듯하면서도 아쉬운 문제였습니다.

새로운 그래프를 그리는 것 까진 좋았으나 이상하게 다익스트라에 꽂혀 오래걸렸습니다.

진작에 완탐 돌렸으면 빨랐을 것을...

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/4991_%EB%A1%9C%EB%B4%87%20%EC%B2%AD%EC%86%8C%EA%B8%B0.cpp

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

문제 이해

N개의 집이있고 3가지의 색으로 집을 칠할 수 있습니다. 연속된 두 집은 같은 색으로 칠할 수 없고, 집마다 각각의 색으로 칠하는 비용이 주어집니다. N개의 집을 조건에 맞게 칠하는 가장 적은 비용을 찾는 문제였습니다.

입출력 조건

0.5초의 시간제한이였으며 N은 최대 1000까지 가능했습니다.

풀이

단순하게 생각하였을 때 지금 칠한 집 다음집은 현재의 집 색이 아닌 다른색을 칠하면 되었습니다. 다른 색이라 해봤자 2가지가 있으므로 다음 집을 칠하는 다른 두 색의 비용을 비교해 현재까지의 비용에 더해주면 되는 전형적인 DP 문제였습니다.

dp[1001][3]으로 배열을 잡았으며 dp[현재 칠하고있는 집][색상]으로 표현하였고 값은 현재 집 까지의 비용을 적어 주었습니다.

이해를 돕기 위한 예시의 일부분 입니다.

앞선 색과 다른 색의 두가지를 비교하여 더 작은 값을 더해서 넣어주면 됩니다.

에러 및 느낀 점

전형적인 DP 문제였기에 규칙만 잘 찾는다면 어렵지 않은 문제라고 생각합니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1149_RGB%EA%B1%B0%EB%A6%AC.cpp

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

문제 이해

여러개의 섬이 있고 여러개의 양방향 다리가 있으며, 해당 다리는 통과할 수 있는 차량의 최대 중량이 정해져 있습니다. 주어지는 2개의 섬이 서로 이동하려고 할때 최대로 가지고 갈 수 있는 중량을 구하는 문제였습니다.

입출력 조건

섬의 최대 갯수는 10,000, 다리의 최대 갯수는 100,000개 였습니다. 또, 중량의 최대 크기가 1,000,000,000(10억) 이였기에 단순히 탐색을 한다면 시간초과가 날것이라 생각하였고, 이분탐색으로 문제를 해결하면 되겠다 싶었습니다.

풀이

앞서 입출력 조건에서 보았던 것 처럼, bfs를 돌려서 해당 지점까지 갈수 있는지의 여부를 구하고, 중량의 무게는 이분탐색으로 찾아주면 logN의 시간에 찾을 수 있기에 어렵지 않게 풀 수 있을거라 생각하여 문제를 해결하였습니다.

에러 및 느낀 점

이분탐색을 몰랐다면 시간초과로 고생하지 않았을까 하는 생각이 들었습니당

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1939_%EC%A4%91%EB%9F%89%EC%A0%9C%ED%95%9C.cpp

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

문제 이해

N개의 도시와 M개의 단방향 도로가 존재합니다. 이때 X번 도시에서 시작하여, "최소거리"가 K인 도시들을 구하는 문제였습니다.

입출력 조건

도시의 갯수는 최대 300,000개 였으며 도로의 최대 갯수도 1,000,000개 였습니다. 시간제한도 2초였기에 bfs를 돌리면 되겠다 생각하였습니다.

풀이

이동한 횟수를 유지해주며 bfs를 돌리면 되는 간단한 문제였습니다.

에러 및 느낀 점

문제를 제대로 읽지 않아 오름차순 정렬이 아닌 되는대로 출력을 하였다가 한번 "틀렸습니다"가 나왔습니다..문제를 잘 읽읍시다ㅜㅠ

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/18352_%ED%8A%B9%EC%A0%95%20%EA%B1%B0%EB%A6%AC%EC%9D%98%20%EB%8F%84%EC%8B%9C%20%EC%B0%BE%EA%B8%B0.cpp

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

문제 이해

선행관계가 있는 작업들이 존재하고, 선행관계가 없는 작업들은 동시에 수행이 가능합니다. 그럴 때 모든 작업을 완료하기 위한 최소 시간을 구하는 문제였습니다.

입출력 조건

최대 작업의 갯수는 10,000개 였으며 시간 제한은 2초 였습니다.

풀이

선행관계가 있다는 점에서 위상정렬을 생각하게 되었고 priority_queue를 이용해 in_degree가 0개인 것부터 넣어주며 pq에는 앞선 작업을 수행한 시간과 자기 자신이 수행되는 시간을 합친 수행시간을 함께 유지하여 순서대로 문제를 처리해 주었습니다.

기본적인 위상정렬 문제였다고 생각됩니다.

에러 및 느낀 점

위상정렬을 알고있다면 쉽게 풀수 있는 문제 였습니다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/2056_%EC%9E%91%EC%97%85.cpp

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

문제 이해

건물들이 주어지고 해당 건물을 짓기위해서는 먼저 지어야 하는 건물들이 주어집니다. 또 건물을 짓는 시간이 주어지고, 입력에서 주어지는 하나의 건물을 짓기 위한 최소 시간을 구하는 문제 였습니다.

입출력 조건

건물의 갯수는 최대 1000개, 순서 조건의 갯수는 100,000개,  건물이 올라가는데 걸리는 시간은 0에서 100,000 사이로 주어집니다. 시간 제한은 1초였습니다.

풀이

순서조건이 제공되는 점에서 위상정렬을 쉽게 떠올릴 수 있었습니다.(위상정렬을 배운지 얼마 안되었기 떄문에) 이 역시 건물을 정점으로 두고, 순서 조건을 간선으로 생각하여 문제를 풀었습니다.

앞선 정점에서 뒤의 정점으로 이동할 때는 앞선 정점에서의 시간과 뒤쪽 정점에서의 시간을 합쳐서 유지해 주었고, 최소 시간을 구해야 했기에 priority_queue를 이용하였습니다.

에러 및 느낀 점

정답이 잘 나왔는데 계속 OutofBounds에러가 발생하였습니다.

이유를 알수 없어, 하나씩 수정하다가 verctor의 resize를 없애고 vector<int> v[1002]로 사용하니 성공하였습니다....

이유는...N을 입력받기 전에 N으로 resize를 해주었기 떄문이였습니다...사소하죠 하하..

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1005_ACM%20Craft.cpp