[SW Expert Academy] 1211. Ladder2

[SW Expert Academy] 1211. Ladder2

문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14BgD6AEECFAYh&categoryId=AV14BgD6AEECFAYh&categoryType=CODE

나의 풀이

1. 출발지점을 찾아야 하기 때문에 도착지점에서부터 탐색한다.

2. 출발지점까지 움직이면서 움직인 거리를 저장한다.

3. 출발지점에 도달했을 때, 움직인 거리가 저장된 최소 거리보다 작다면 최소 거리와 출발 지점을 갱신한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/SW_Expert_Academy_1211/SW_Expert_Academy_1211.cpp

// [S/W 문제해결 기본] 1211. 2일차 - Ladder2
#include<iostream>
#include<cstring>
using namespace std;
 
 
int ladder[101][101];
int visited[101][101];
int dis, departure;
 
// 왼쪽, 오른쪽, 위
int dx[3] = {0, 0, -1};
int dy[3] = {-1, 1, 0};
 
void finddeparture(int _x, int _y)
{
    int local_distance = 0;
    int x = _x;
    int y = _y;
    
    while (1)
    {
        if (x == 0) {
            if (dis > local_distance)
            {
                dis = local_distance;
                departure = y;
            }
            return;
        }
        for (int i = 0; i < 3; i++)
        {
            int mx = x + dx[i];
            int my = y + dy[i];
 
            if (mx < 0 || mx >= 100 || my < 0 || my >= 100) continue;
            if (ladder[mx][my] == 0) continue;
            if (visited[mx][my]) continue;
            x = mx;
            y = my;
            local_distance++;
            visited[mx][my] = 1;
            break;
        }
    }
    return;
}
 
int main(void)
{
    int num;
 
    for (int T = 1; T <= 1; T++)
    {
        memset(ladder, 0, sizeof(int) * 101 * 101);
        dis = 10000;
        cin >> num;
 
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++)
            {
                cin >> ladder[i][j];
            }
        }
 
        for (int i = 0; i < 100; i++) {
            memset(visited, 0, sizeof(int) * 101 * 101);
            if (ladder[99][i]) finddeparture(99, i);
        }
 
        cout << '#' << num << ' ' << departure << '\n';
    }
    return 0;
}