Hyun's_Devlog

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

그래프 탐색 문제다.

풀이

모눈종이의 가장자리에는 치즈가 없다. 즉 (0,0) 좌표부터 너비우선탐색을 수행하여 치즈를 마주치면 해당 좌표를 저장. 탐색도중 같은 좌표를 한번 더 마주하게 된다면 해당 치즈는 2변이 실내온도에 닿은 것으로 판정하여 녹은 것으로 판정한다. 좌표를 저장하고 탐색하는 데에 O(1)만에 탐색이 가능한 Set 자료구조를 사용하였다. 치즈의 개수가 0이 될 때까지 탐색을 수행. 반복이 일어난 횟수를 출력하면 된다.

정답 코드

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

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

풀이

너비우선탐색을 수행한다. 다익스트라 알고리즘의 특성상 우선순위 큐를 사용해서 풀어야 하지만, 문제의 N값이 크지 않기에 배열을 정렬하여 풀어도 시간초과는 피할 수 있다. 스위프트의 경우 우선순위큐를 직접 구현해야하기에 귀찮다.

방문여부를 저장할 2차원 visited 배열, 각 좌표에 도둑루피의 값을 담을 2차원 map 배열과 해당좌표까지의 최저 cost를 담을 2차원 cost배열을 생성한다. cost 배열은 INF로 초기화한 뒤 탐색을 수행한다. 

x, y, cost 정보를 담아낼 배열을 생성한다. 배열에서 cost가 가장 작은 좌표를 먼저 방문하여 (현재 좌표의 cost + 인접배열의 cost값)을 계산하여 인접배열의 cost를 더 작은 값으로 갱신한다. 다음 탐색에 cost가 가장 작은 값을 방문해야 하니 매 반복문의 마지막에는 큐를 정렬해 준다.

탐색이 끝나면 목적지인 cost배열의 가장 마지막 값을 출력하면 된다.

정답 코드

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

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

풀이

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

정답 코드

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을 반환해야 한다.

정답 코드

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

그래프 탐색 문제다. 너비 우선 탐색으로 풀었다. 상어의 움직임에 대해 오래 고민했던 문제다.

풀이

상, 좌, 우, 하 순서로 너비 우선 탐색을 수행한다. 빈 곳이거나 같은 사이즈의 물고기를 만난다면 큐에 담아 이동을 수행, 자신보다 작은 사이즈의 물고기를 만나면 해당 좌표를 다른 배열에 저장하였다.

탐색이 끝난 뒤 문제의 조건에 맞게 먹을 수 있는 물고기가 담긴 배열을 시간, x좌표, y좌표 순으로 정렬한 뒤 가장 가까운 좌표로 이동하여 해당 물고기를 먹으면 된다. 처음에는 이러한 정렬 없이 먹을 수 있는 물고기를 만나면 바로 먹어버리고 탐색을 종료했는데, 같은 거리에 있는 먹을 수 있는 물고기에 대한 조건이 안 맞아 오답이 나왔다.

탐색 함수는 상어가 이동한 좌표와 걸린 시간을 반환하게 하였다. 상어의 좌표에 이동이 없는 경우 먹을 수 있는 물고기가 없는 것으로 판단하여 반목문을 빠져나오는 것으로 코드를 작성했다.

정답 코드

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

그래프 탐색 문제다. 너비 우선 탐색으로 해결했다.

풀이

0부터 9999에 해당하는 움직임을 담는 문자열 배열을 생성한 뒤, 입력되는 A부터 시작하여 너비 우선 탐색을 수행한다. D, S, L, R 연산에 해당하는 숫자를 만들고 해당 인덱스의 배열에 현재까지의 움직임에 해당 움직임 문자열을 더하여 탐색을 수행한 뒤 탐색이 끝나면 B인덱스의 배열 값을 출력하면 된다.

정답 코드

시간초과를 마주하여 조금 더 동작을 빠르게 해결하기 위해 27번 라인에 B번째 배열의 값이 갱신되면 탐색을 곧바로 종료하는 조건을 추가하였다.