백준 1189번 컴백홈

🔒[문제 url]

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

🪄전체 코드

#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;

int r,c,k;
char map[6][6];
int visited[6][6];
int dir[4][2] = {{0,-1},{0,1},{-1,0},{1,0}}; // 좌 우 상 하
int ans = 0;

void INPUT()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> r >> c >> k;
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            scanf("%1s", &map[i][j]);
}

void DFS(int x, int y)
{
    if(x == 0 && y == c - 1)
    {// 집에 도착했을때
        if(visited[x][y] == k) ans++; // 이동거리가 k라면 ans를 1 증가시킨다.
        return;
    }

    for(int i = 0; i < 4; i++)
    {
        // 다음 경로 설정
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if(0 <= nx && nx < r && 0 <= ny && ny < c)
        {// check range
            if(visited[nx][ny] == 0 && map[nx][ny] != 'T')
            {// 방문하지 않았던 곳이고 T(가지 못하는 지점)이 아니라면
                visited[nx][ny] = visited[x][y] + 1; // 경로를 1만큼 증가시키고
                DFS(nx,ny); // 이어서 탐색한다.
                // BackTracking
                visited[nx][ny] = 0;
            }
        }
    }
}

void SOLVE()
{
    memset(visited,0,sizeof(visited));
    visited[r-1][0] = 1; // 왼쪽 아래에서 시작

    DFS(r - 1, 0);
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.