Hyun's_Devlog

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

그래프 탐색과 조합론으로 접근했다.

풀이

기본적인 그래프 탐색 문제와의 차별점은 지나가면 안 되는 간선이 주어진다는 점이다. 해당 부분을 어떻게 저장하고 핸들링할지 고민해하는 것이 이번 문제의 핵심.

인접행렬은 상, 하, 좌, 우로 4방향을 따져야 하므로 map[x좌표][y좌표][넘어갈 수 있는 방향 정보] 형태의 3차원 배열을 생성하였다. 즉 N*N*4 배열을 통해 너비우선탐색을 수행하여 해당 소가 방문하지 못하는 좌표에 다른 소가 있다면 문제에서 요구하는 답으로 판정하였다.

문제에서 요구하는 것은 길을 통해 건너야만 만날 수 있는 '쌍'을 찾는 것이니 중복을 없애기 위해 K에서 2개를 뽑는 조합 반복문을 통해 그래프탐색을 수행하였다.

정답 코드

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

다익스트라 알고리즘으로 접근한 문제다.

풀이

출발지와 목적지가 이미 정해져 있는 문제이므로 거리정보를 담아둘 배열을 생성. 최대 비용 250000(500*500) 보다 큰 250001로 초기화시켜 둔다. 출발지 (0,0)은 이미 도착한 것이므로 비용을 0으로 시작. 너비우선탐색을 수행하여 비용이 더 적게 드는 경우 비용을 갱신하고 해당 좌표를 큐에 담아 탐색을 수행하면 된다. 탐색이 끝나면 가장 마지막 위치의 비용을 출력하면 된다.

정답 코드

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

[2610] 회의준비와 결이 비슷한 문제다. 

풀이

유니온파인드와 그래프탐색으로 접근했다. 가중치가 큰 순으로 간선을 정렬한 뒤 순서대로 유니온을 수행, 루트가 같다면 결합하지 않는다.

이후 입력되는 출발지와 도착지를 기준으로 너비우선탐색을 수행. 그래프를 탐색하면서 가중치를 수정해나가면 된다. 

처음에는 (k횟수만큼) 그래프와 루트정보를 매번 초기화하고, 입력되는 출발지와 도착지를 기준으로 유니온을 하면서 그래프를 탐색했으나, 시간초과발생. 생각해보니 간선을 한 번만 탐색하고도 cost를 출력할 수 있게 접근이 가능했었다.

정답 코드

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

너비우선탐색으로 접근한 문제다.

풀이

입력받은 지뢰의 충격이 큰 순서부터 터트리면서 너비우선탐색을 수행한다. 이때 터트리는 지뢰의 번호를 입력받은 뒤 오름차순으로 정렬하여 출력하면 된다.

정답 코드

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

유니온 파인드 문제다. 추가적으로 그래프 탐색을 통해 접근했다.

풀이

문제에 "지도 밖으로 나가는 방향은 주어지지 않는다"는 입력 조건이 있다. 그 얘기는 주어지는 좌표 어느 부분이던 탐색 시 무조건 사이클이 일어난다는 것이고, 문제의 답은 사이클이 일어나는 영역에 하나씩 "safe zone"을 설치하면 된다는 이야기. 요약하자면 깊이 우선 탐색을 통해 유니온파인드를 통해 컴포넌트의 개수를 반환하면 되는 것이다.

예제의 입력을 기준으로 사이클이 일어나는 영역을 색으로 표시해 놓았다. 두 개의 구역으로 나뉘며, 구역 하나당 하나의 "safe zone"을 설치하면 최소 개수를 구할 수 있다.

고민했던 점은 유니온을 할 때, 어떻게 구별하느냐인데, 이전에 풀었던 문제에서 2차원 배열을 번호로 매겨서 1차원 배열에 대입하여 풀었던 기억이 나서 그 부분을 사용했다. 즉 깊이 우선 탐색을 하면서 해당 위치의 번호와 다음 위치의 번호를 유니온, 루트가 같다면 종료. 모든 좌표에 대해서 깊이 우선 탐색을 수행한 뒤, 컴포넌트의 개수를 출력해주면 된다.

정답 코드

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

그래프 탐색 문제다. 너비 우선 탐색을 통해 4회 이상의 탐색이 이루어졌다면 연쇄 횟수를 증가시키고 연쇄가 일어난 곳은 다음 원소로 메꾸는 방식으로 접근했다.

풀이

문제에서는 연쇄가 일어난 이후 상단에서 하단방향으로 원소를 매꾸어 주어야 하기에, 다루기 편하게 12 x 6 배열이 아닌 6 x 12 크기의 배열로 구현하여 탐색을 진행했다. 

문제에서 요구하는 것은 연쇄가 몇번 일어났는지가 아닌, 연쇄 사이클이 몇 번 이루어졌는지 이기 때문에, while문과 flag를 통해 사이클 횟수를 세고, 연쇄가 일어나지 않는다면 반복문을 빠져나가는 것으로 코드를 작성했다. 

탐색 수행시, 본 배열을 임시 배열에 담은 후 임시 배열을 탐색하였다. 탐색한 곳은 "#" 문자열로 변경, 4번 이상의 변경이 이루어지면 해당 배열을 본래 배열에 반영해주는 방법으로 너비 우선 탐색을 진행했다.

한 사이클의 탐색이 끝나면 또다시 임시 배열을 생성하여 빈 공간과 문자열을 분리하여 담아낸 뒤 [문자열] + [빈 공간] 배열을 붙여 본 배열에 반영해주었다.

정답 코드

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

그래프 탐색으로 접근한 문제다. 

풀이

파이프의 앞쪽을 head, 뒤쪽을 tail로 설정하여 tail과 head의 x, y좌표를 비교하여 수평 이동해야 할지, 수직 이동해야 할지, 대각선 이동을 해야 할지 비교한 후 탐색을 통해 해결하였다. 

파이프가 수평으로 놓인 경우

head의 x좌표와 tail의 y좌표가 맞는지 확인하면 된다. 동일하다면 파이프가 수평으로 놓인상태, 이경우에는 수평이동, 대각선 이동이 가능하다.

파이프가 수직으로 놓인 경우

head의 x좌표와 tail의 x좌표가 다르고 y좌표가 서로 다르다면 수직으로 놓인 경우다. 이경우에는 수직이동, 대각선이동이 가능하다.

파이프가 대각선으로 놓인 경우

당연하게도 head와 tail의 x좌표 y좌표가 모두 다른경우다. 이경우에는 3가지 이동을 모두 수행하면 된다.

이동을 수행할 때에는 이동할 좌표가 유효한 범위인지, 그리고 벽이 아닌 빈 공간인지를 확인하고 탐색 큐에 담아주었다.

정답 코드

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

숨바꼭질 시리즈이다. 그래프 탐색으로 접근 가능한 문제다. 

풀이

실수를 유발하게 하는 포인트가 몇가지 있다. 우선 문제에 동생과 수빈이가 위치한 좌표만 적혀있을 뿐 어디까지 이동이 가능한지 제약이 적혀있지 않다. 즉 동생의 좌표 최댓값 100000보다 더  큰 범위로 순간이동 후 걸어와서 발견하는 방법이 존재한다는 것이다. 역으로 돌아오는 것은 걸어오는 방법(-1) 밖에 없기에 최대 유효 범위는 100001이다. 그보다 큰 위치에서 돌아오는 방법은 최소 시간을 갱신할 수 없다. 따라서 100002개의 배열을 생성한 뒤 한 칸 후퇴, 한 칸 전진, 두배 순간이동의 방법으로 너비 우선 탐색을 수행하면 된다. 

다음으로 중요한 부분은 같은 시간이 걸리더라도 걸어가서 동생을 마주하는 방법과 순간이동으로 마주하는 방법은 다르게 계산해야한다는 점이다. 따라서 도달하게 된 시간이 같다면 도달 방법 수 갱신만 하지 말고 다음 탐색 큐에 담아주어야 한다.

마지막으로 이동하지 않는 것도 방법으로 세야 한다는 것이다. 즉 처음부터 동생과 수빈이의 위치가 같은 경우라면 1을 반환해야 한다.

정답 코드