[Softeer] GINI야 도와줘(Lv.3) - Day5

📋 개요 

4일차는 dp에 관련된 문제였다. LCS, 점화식 찾기와 같은 문제였고, Day 5에 진행되는 문제는 완탐과 그리디? 같은데 사실 정확히는 잘 모르겠다. 알고리즘을 전문적으로 배우지는 않았어서, 내눈에는 다 구현처럼 보인다.

2024.01.29 - [Algorithm/Problem] - [Softeer] 비밀메뉴2(Lv.3) - Day4

2024.01.29 - [Algorithm/Problem] - [Softeer] 지도 자동 구축(Lv.2) - Day4

[Softeer] 지도 자동 구축(Lv.2) - Day4

[Softeer] 비밀메뉴2(Lv.3) - Day4

 

이번에 풀이해볼 문제는 'GINI야 도와줘' Lv.3문제이다. 문제만 딱 읽어도 bfs로 풀어야할거 같다.

https://softeer.ai/practice/6271

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

---

🧩 문제

GINI는 현대자동차그룹에서 개발한 네비게이션이다. GINI는 너무나도 뛰어나 목적지에 도착하는 시간을 예측할 수 있다. 어느 날 태범이는 세차장에서 세차를 하고 집에 돌아가려고 하는데 소나기가 몰려오고 있다는 뉴스를 전해 들었다. 태범은 방금 세차한 차를 지키기 위해 GINI를 사용하여 무사히 집에 귀환하고자 한다!

 

지도는 R행과 C열로 이루어져있다. 비어있는 칸은 ‘.’로 표시되고, 소나기는 ‘*’로, 강은 ‘X’로 표시되어있다. 태범이의 집은 ‘H’로 표현되고, 태범이가 처음있던 세차장의 위치는 ‘W’로 표시된다.

 

매 분마다 태범이는 인접한 네 개의 칸(상, 하, 좌, 우)으로 이동할 수 있다. 소나기는 매 분마다 인접한 네 개의 칸(상, 하, 좌, 우)으로 확산한다. 태범이는 소나기와 강을 지나지 못하며, 소나기는 강과 태범이의 집에 옮겨지지 않는다.(소나기는 강으로 가면 소멸) 태범이가 무사히 집에 도착할 수 있을 때 몇 분 만에 도착할 수 있는 예측하는 GINI 네비게이션 프로그램을 만들어보자.

⛔ 제약조건

R, C ≤ 50

‘H’와,’W’는 하나씩만 주어진다.

📝  형식 

📥 입력	📤 출력
첫째 줄에 R과 C가 주어진다. 다음 N개 줄에는 지도가 주어지며, 문제에서 설명한 문자만 주어진다.	첫째 줄에 태범이가 집으로 갈 수있는 가장 빠른 시간을 출력한다. 만약 소나기를 피해 집에 도착할 수 없다면 “FAIL”을 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1		FAIL
2		2

🖥️ 내 코드

---

📖  해설 및 느낀점

# 코테 유형 - 상하좌우

// 상, 하, 좌, 우 이동을 위한 배열
int deltaX[4] = {0, 0, 1, -1};
int deltaY[4] = {-1, 1, 0, 0};

 

코딩테스트를 풀다보면 상하좌우처럼 좌표계를 순서대로 이동하는 문제들이 대부분 많이 나온다. 처음에는 상하 좌우를 어떻게 표현해야하는건지, 상 (0,1), 하 (0,-1) 좌 (1,0) 우(-1,0)이라고 생각 할 수 있지만 우리가 방향성이 있다고 생각하고 좌표를 바라보고 생각해보자

많은 BFS관련 문제나 좌표 이동 문제를 풀다보면 dx,dy를 설정해서 이동하는 문제의 유형이 많다. 항상 문제를 풀면서 헷갈리는건 기존 수직 좌표계를 생각해서 상하좌우가 헷갈린다는 것이다. 그래서 위에 그림을 보면 우측이 우리가 방향 배열을 선언할때 보여주는 값이다. 

 

어떻게 생각을 했냐면 우리가 원하는 값을 중간에 넣고 그 원하는 값이 되기 위해 "변화량"을 확인하면된다. 4가지 이동방향 뿐만아니라 8방향으로 움직이는 것도 나오기 때문에 같이 달아두었다.

(상하좌우 순으로 문제가 나오는게 아니니 응용해서도 알고 있어야한다. 하우좌상 순으로 나오거나 우좌하상 순서가 바뀌어서 나올때도 있기때문에 알고있어야한다.)

 

# 코테 유형 - BFS

자주 나오는 유형중에 하나는 BFS로 경로 탐색 문제가 자주 등장하게 된다. 아래는 내가 BFS와 DFS관련해서 작성한 포스팅이니 참고하면 좋을거 같다.

2023.09.22 - [Algorithm/Concept] - [Algorithm] 탐색 - DFS와 BFS

[Algorithm] 탐색 - DFS와 BFS

 

해당 문제는 길찾기 문제이다. 길찾기는 거의 대게 그래프 탐색인 bfs를 통해서 해결할 수있다. bfs는 Queue를 사용해서 구현을 할 수 있다. 꼭 기억하면 좋다. bfs = Queue이다.

# 문제풀이

이런 구현문제는 먼저 함수별로 나누어야한다. 우리는 문제를 읽어보면 어떤 함수별로 쪼개야하는지 찾을 수 있다.

1. 입력 - 이 친구는 항상 기본으로 들어가는게 좋다.
2. 태범이가 집으로 가는 경로 찾기 - bfs
   1. 소나기 확산
   2. 태범이 이동
3. 출력 - 입력과 마찬가지로 항상 기본으로 들어가는게 좋다. 결국 출력이 답이니깐...!

이렇게 작성을 하면된다.

 

#include <iostream>
#include <queue>
using namespace std;

// 입력을 읽는 함수
void input();

// 소나기 확산 로직을 처리하는 함수
void spreadStorm(queue<pair<int, int>>& queueStorm);

// 태범이 이동 로직을 처리하는 함수
bool moveTaebum(queue<pair<int, int>>& queueTaebum, int& timeElapsed);

// 태범이가 집으로 가는 경로를 찾는 메인 함수
void navigateToHome();

int main() {
    input(); // 입력 받기
    navigateToHome(); // 태범이가 집으로 가는 경로 찾기
    return 0;
}

 

출력은 FAIL도 출력해야하고 해서 어떤식으로 빼야할지 모르겠어서 따로 빼지는 않았지만 따로 빼는게 좋다고 한다. 항상함수를 먼저 분리하고 내가 작성해야할 코드들에 대해서 명확히해야 구현하는데 큰 어려움이 없다고 한다. 함수를 나눠서 작성하는게 시간이 오래걸린다고 생각할 수 있지만 나중에 안풀린다면 찾아내야하기 때문에 꼭 쪼갤 수 있도록 하자.

(리팩토링하면서 출력을 한번 빼봐야겠다.) 그리고 조건에 맞게 if문을 작성해주면 된다.

 

bfs를 풀이할때는 항상 visited(방문) 노드가 필요해서 선언을 하여서 진행을 해야한다. 하지만 이 문제는 bfs알고리즘이 2개가 사용된다. 소나기와 태범이의 방문 노드!

 

그리고 위에서 설명한 상하좌우순서대로 진행을 하면서 태범이와 소나기 확산을 해주면된다.

 

해당 문제는 생각보다 난이도가 있었다. 내가 bfs탐색을 많이 안풀어봐서 그런거 같다. 그래서 bfs는 큐를 이용해서 방문 노드를 활용해서 풀이해야한다는 것만 알고 있었다면 조건을 하나씩 찾아나가면서 푸는건 그렇게 어려울거 같지는 않다!