구름톤 챌린지 | 4주차 학습일기 [19일차 / 20일차]

구름톤 챌린지 코딩테스트 4주차 학습일기입니다.

4주차 학습일기

구름톤 챌린지 4주차

Day19 대체경로

문제 분석

N개의 마을이 M개의 길로 이어져 있다. 이 길은 양방향으로 연결 돼 있다. i번째 날에는 i  마을이 공사를 하기 때문에 방문할 수 없다. 시작점과 도착지가 주어져 있을 때 날마다 최단 경로가 어떤지를 계산해 출력하는 문제이다.

해결 전략

1. 인접리스트배열을 사용해 마을의 연결 관계를 입력한 뒤 모든 배열리스트를 정렬해준다.

2. 목적지에 도착하면 바로 연산을 멈출 수 있는 BFS(너비 우선 탐색)을 이용해 접근할 수 있는 모든 깊이 체크하며 방문한다. 이 때 하나의 깊이를 들어갈 때마다 카운트를 올려주고 현재 방문중인 마을(노드)를 매번 업데이트 해준다.

2-1. 도착지가 공사중인 마을이거나 출발지와 같은 마을일 경우 카운트 값을 -1로 해 BFS를 종료한다.

2-2. 방문한 칸이 목적지이면 BFS를 중단하고 카운트한 값을 출력한다.

2-3. BFS의 while문이 모두 종료 된 후 마지막 방문한 마을이 최종 목적지가 아니면 카운트 값을 -1로 바꿔준 뒤 출력한다.

배운점

BFS에서 Queue를 사용하는 While을 시작할 때 Queue의 Size를 저장해 놓으면 같은 깊이에 있는 값들만을 다룰 수 있다.

결과

성공했다. 구르미에게 바지를 선물해 주었다.

구름톤 챌린지 결과모습

미션 블록 현황

Day 20 연결 요소 제거하기

문제 분석

N x N 배열이 주어진다. 각 칸에는 알파벳 대문자 또는 . 이 쓰여있다. 상하좌우로 같은 알파벳이 있을 경우 이 알파벳들은 연결돼 그 그룹을 연결 요소라고 부른다. 한 요소에 속한 알파벳의 수를 그 연결 요소의 크기라고 한다. 구름이는 . 이 찍혀 있는 배열의 한 곳을 주어진 알파벳으로 대체할 것이다. 이 때 배열 전체에 있는 연결 요소들의 크기가 주어진 K보다 큰 경우 그 연결 요소의 모든 알파벳을 .으로 변경해 준다.

위 행위를 총 Q번 반복한 후 배열의 모습을 출력하면 된다.

해결 전략

1. 각 점에서 DFS 탐색을 시작한다.

2. 방문한 지점의 .을 주어진 알파벳으로 변경하고 해당 점을 Queue에 넣고 반복문을 시작한다.

3. Queue에서 꺼내서 방문 체크와 위치 정보를 또다른 Queue에 담아둔다. 그리고 카운트를 1 올려준다.

4. 이제 그 점에서부터 상하좌우 탐색을 시작한다. 인접 칸을 살펴봐서 방문한적이 없고 같은 알파벳을 갖고 있다면 칸의 좌표정보를 Queue 담는다.

3. Queue에 남은 원소가 없을 때 까지 위의 3~4를 반복한다.

4. 반복문이 끝난 뒤 카운트 값이 주어진 K 이상인 경우 다른 Queue에 담아둔 위치 정보를 이용해 방문했던 모든 칸의 정보를 .으로 대체한다.

5. DFS가 종료된 뒤 N x N 배열을 출력해준다.

결과

마지막 날까지 드디어 모두 완료했고 구르미에게 트로피를 선사했다.

20일차 미션 성공 모습

20일차 미션 블록 현황

회고

게임 처럼 정말 재밌게 한 달 동안 코딩할 수 있었다. 가장 큰 동기는 구름에서 진행되는 스페셜 세션에 참가하기 위해서였지만 매일 아침 잘 선별된 한 문제씩 풀어서 알고리즘 문제풀이 훈련이 자동으로 됐고 그 내용을 블로그에 적는 습관을 만드는데 도움을 준 것만으로도 정말 재밌고 의미있는 챌린지였다.

구르미 진화

그래프 탐색

특히 그래프 탐색은 정말 약한 부분이었는데 마지막 주에 집중적으로 매일 훈련하면서 정말 많이 익숙하게 됐다. 어려운 난관 하나를 넘은 것 같아 이 점은 정말 뿌듯하다.

감사

바쁜 와중에도 시간 내서 문제를 풀 이유를 만들어 주셔서 구름에게 진짜 감사합니다.