Diary

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

문제이해

직사각형 모양의 연구소가 있고, 연구소에 새로운 벽 3개를 설치하였을 때 바이러스가 퍼지지 않는 안전한 지역의 최대 갯수를 구하는 문제 였습니다. 중요한 점은 꼭 새로운 벽 3개는 필수적으로 설치를 해야한다는 점입니다.

단순히 모든 경우에 있어서 3개의 빈공간을 선택하여 벽을 설치하고, 바이스의 위치에서 bfs를 돈다고 했을 때 시간초과가 날까 걱정했지만 입출력 조건을 보고 가능하다 생각하게 되었습니다.

직사각형의 최대 크기는 8x8 = 64 였으며 벽 3개를 고르는 모든 경우의 수 64C3 = 41664 이며, 매번 모든 공간을 탐색한다고 하였을 때 최대 41664 x 64 = 2666496 으로 충분히 시간내에 가능하였습니다. (사실 크게 계산을 안해봐도 제한이 8이라는 것을 보았을 때 시간 제한은 걸리지 않을 것 같았습니다.)

입출력 조건

시간 제한은 2초, 직사각형의 최대 크기는 64 였고, 위의 식대로 시간초과가 나지는 않을 듯 하였습니다.

풀이

위 방식대로 문제를 해결하였으며 자세한 사항은 코드 내 주석을 참고해 주세요.

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

문제이해

사실 문제를 이해하기가 가장 어려웠습니다. 하여 다른 분들의 풀이를 보고서 문제를 이해할 수 있었습니다. 하나하나 차근차근 보도록 하겠습니다.

1. 거울을 설치하면 45도 기울어진 상태로 설치하게 됩니다 -> 이는 결국 빛이 들어오는 방향의 90도로 빛이 꺾인다는 것을 의미합니다. 그렇기에 빛은 거울을 만나면 들어오는 방향에서 90도로 꺾이는 두가지 방향으로 진행하게 됩니다. (예를 들어 북쪽에서 빛이 남쪽으로 향하다가 거울을 만나면 동쪽 혹은 서쪽으로 꺾이게 됩니다)

2. 시작할 당시 빛의 진행 방향을 알 수 없기 때문에 모든 방향으로 진행됨을 고려해 주어야 합니다.

3. 같은 지점으로 빛이 도착할 지라도, 어떠한 방향에서 들어왔는지에 따라 모두 다른 경우이기 때문에 이를 모두 체크해 주어야 합니다. 예를 들어 빛이 [3,3]에 도착하였을 경우 북쪽으로 부터 들어온 빛인지, 동쪽에서 들어온 빛인지에 따라 모두 다른 경우가 됩니다. 그렇기에 visit 배열 같은 경우 3차원 배열로 생각하는 것이 편한 방법이였습니다. (예를 들어 visit[A][B][C]는 [A,B]좌표에서 C방향으로 빛이 진행할 때 설치한 거울의 갯수가 되도록 하였습니다)

이제 문제를 풀어보겠습니다.

입출력 조건

시간 제한은 2초, 집의 최대 크기는 50x50 이였기에 4방향을 모두 탐색하여 50x50x4가 되어도 시간을 초과할 일이 없었습니다.

풀이

 위 문제 이해를 바탕으로 BFS를 이용해 문제를 해결하였으며 자세한 세부사항들은 코드에 주석을 달아 놨습니다.

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

문제 이해

RxC 크기의 격자가 주어지고 봄버맨은 그 위에 살고 있습니다. 봄버맨이 폭탄을 설치하고 폭탄은 3초후에 폭발하며 매초 빈칸은 폭탄이 설치 됩니다. 폭탄은 연쇄 폭발을 일으키지 않으며 최초 1초는 아무일도 일어나지 않습니다. 이때 N초만큼 시간이 흐른후의 격자판의 모습을 구하는 문제였습니다.

입출력 조건

R,C,N 은 모두 200이 최대였으며 시간초 제한은 2초였습니다.

풀이

R,C,N이 모두 200이 최대 였기에 완탐을 돌려도 200x200x200 이면 800만 정도이기에 충분하다 생각하여 순전히 구현으로 문제를 해결하였습니다.

에러 및 느낀 점

0과 O가 구분이 잘 안갑니다...

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16918_%EB%B4%84%EB%B2%84%EB%A7%A8.cpp

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

문제 이해

그래프가 주어지고 해당 그래프에서 모든 정점을 연결하면서 가중치의 합이 가장 작은 그래프의 가중치의 합을 구하는 문제였습니다.

입출력 조건

시간초 제한은 2초였으며 최대 정점의 갯수는 1,000개 였습니다.

풀이

당연히 MST 문제라고 생각을 하였고 실제로 그렇게 구현했습니다.

기본적인 MST 문제였습니다.

에러 및 느낀 점

.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1922_%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%20%EC%97%B0%EA%B2%B0.cpp

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

문제 이해

친구 관계의 수 F가 주어지고 F줄 만큼 친구 관계가 주어질 때, 해당 친구관계가 주어질 때 마다 연결되어 있는 친구 관계의 수를 출력하는 문제였습니다.

입출력 조건

시간초 제한은 3초였으며 최대 친구관계의 수는 100,000개 였습니다. 이에 따라 나올 수 있는 최대 인원의 수는 200,000이라는 것을 알 수 있습니다.

풀이

일반적인 유니온 파인드에  부모 배열과 함께 친구의 수를 저장하는 배열을 같이 두면 되겠다고 생각했습니다.

매번 들어올 때마다 두 친구를 유니온 해주고, 유니온 할때 한쪽의 친구 수를 0으로 만들고 다른쪽으로 합쳐줬습니다.

또 문자열로 입력이 들어왔기에 map을 이용하여 번호를 부여해 주었습니다.

에러 및 느낀 점

처음에 친구관계가 최대 100,000개라 해서 배열을 100,000까지만 잡고 했다가 Out of Bounds가 떴었습니다ㅠ

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/4195_%EC%B9%9C%EA%B5%AC%20%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC.cpp

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

문제 이해

양방향 그래프가 하나 주어지고 해당 그래프의 정점 1에서 부터 BFS를 수행하였을 때 예상했던 순서로 정점이 출력이 되는지를 묻는 문제였습니다.

입출력 조건

시간제한은 2초에 정점은 100,000개 까지였습니다.

풀이

앞서 풀었던 DFS 스페셜 저지 문제와 똑같은 문제에 dfs -> bfs로 바뀐 문제였기에 앞의 문제 풀이 링크를 참고해 주시면 감사하겠습니다.

https://tory-do.tistory.com/57

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16940_BFS%20%EC%8A%A4%ED%8E%98%EC%85%9C%20%EC%A0%80%EC%A7%80.cpp

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

문제 이해

양방향 그래프가 하나 주어지고 해당 그래프의 정점 1에서 부터 DFS를 수행하였을 때 예상했던 순서로 정점이 출력이 되는지를 묻는 문제였습니다.

입출력 조건

시간제한은 2초에 정점은 100,000개 까지였습니다.

풀이

이게 뭔 문제인가 싶었습니다.. 그냥 DFS를 구현했고 돌려서 비교하면 되는거 아닌가..해서 했더니 아니나 다를까 그렇게 쉬운문제는 아니였습니다.

간선들 사이에 우선순위가 정해져 있지 않았기 때문에 여러가지의 답이 나올 수 있는 상황이였습니다.

그래서 예상 순서를 받았을 때 이를 배열에 따로 저장하고 이들이 나온 순서를 또 배열로 저장하여 앞서 나온 순서들이 먼저 DFS에 들어갈 수 있도록 정렬해 주었습니다.

그리고 제출했더니..100퍼센트에서 틀렸습니다가 떴습니다..아무리 봐도 맞는거 같은데 뭐지뭐지 하다가 

해당 줄을 계속 보다보니 이게 시작정점이 1이여야만 한다는 건가..? 라는 생각이 들었습니다.

그래서 1이 아닌경우는 그냥 0을 출력하고 끝내는 코드로 수정 후 제출해 보니 맞았습니다가 떴습니다..

어이 없었슴다ㅜ

에러 및 느낀 점

문제 설명이 조금 더 정확히 있었으면 어땠을까 하는 생각이 들었습니다ㅠ

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16964_DFS%20%EC%8A%A4%ED%8E%98%EC%85%9C%20%EC%A0%80%EC%A7%80.cpp

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

문제 이해

단방향 그래프가 주어지면 해당 그래프의 간선들을 지워 2개의 다른 그래프로 만들어야 했습니다. 하지만 각각의 그래프는 모두 연결되어 있어야 하며 간선의 가중치의 합이 가장 적도록 하는 문제였습니다.

입출력 조건

시간초 제한 2초, 정점의 수는 최대 100,000개까지 가능했습니다.

풀이

모두 연결되어 있으면서 간선의 가중치들의 합이 가장 작아야 한다는 것은 결국 최소 스패닝 트리를 구하는 문제였습니다.

하지만 2개의 그래프로 나눠야 한다는점에서, 그냥 최소 스패닝 트리를 구하고, 가장 큰 간선 하나를 짜르면 되는 것 아닌가 라고 생각했는데 맞았습니다....단순한 최소 스패닝 트리 문제였습니다.

에러 및 느낀 점

.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/1674_%EB%8F%84%EC%8B%9C%20%EB%B6%84%ED%95%A0%20%EA%B3%84%ED%9A%8D.cpp