[21.08.31] DFS 연습하기

- 땅 팔때마다 땅값 *3 %10으로 바뀜, 3곳의 땅값의 합이 가장 큰경우 찾기

#include<iostream>
#include<cstring>
using namespace std;
int map[3][3] =
{
    4,1,7,
    8,9,1,
    1,5,2
};
int Max = -21e8;
void digging(int y,int x)
{
    int direct[5][2] = { 0,0,-1,0,1,0,0,-1,0,1 };
    for (int t = 0; t < 5; t++)
    {
        int dy = y + direct[t][0];
        int dx = x + direct[t][1];
        if (dy < 0 || dx < 0 || dy>2 || dx>2)continue;
        int n = map[dy][dx] * 3;
        map[dy][dx] = n % 10;
    }
}
int getsum()
{
    int sum = 0;
    for (int y = 0; y < 3; y++) {
        for (int x = 0; x < 3; x++)
        {
            sum += map[y][x];
        }
    }
    return sum;
}
void abc(int level)
{
    int backup[3][3];
    if (level == 3)
    {
        int result = getsum();
        if (result > Max)
        {
            Max = result;
        }
        return;
    }

    memcpy(backup, map, sizeof(map));
    for (int y = 0; y < 3; y++)
    {
        for (int x = 0; x < 3; x++)
        {
            digging(y, x);
            abc(level + 1);
            memcpy(map, backup, sizeof(backup));
        }
    }
}
int main()
{
    abc(0);
    cout << Max;
    return 0;
}

- ABTK -> AKTB 변환하는데 걸리는 최소횟수

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string start = "ABTK";
string target = "AKTB";

void lspin()
{
    char temp = start[0];
    start[0] = start[1];
    start[1] = start[2];
    start[2] = start[3];
    start[3] = temp;
}

void rspin()
{
    char temp = start[3];
    for (int t = 3; t > 0; t--)
    {
        start[t] = start[t - 1];
    }
    start[0] = temp;
}
void tover()
{
    char temp[4];
    for (int t = 0; t < 4; t++)temp[3 - t] = start[t];
    for (int t = 0; t < 4; t++)start[t] = temp[t];
}
int Min = 99999;
void abc(int level)
{
    if (start == target)
    {
        if (Min > level)Min = level;
        return;
    }
    if (level == 4)return;  // 주의: 설계시 리턴조건 잘 생각해서 주석달아 놓을 것
    lspin(); abc(level + 1); rspin();
    rspin(); abc(level + 1); lspin();
    tover(); abc(level + 1); tover();
}

int main()
{

    abc(0);
    cout << Min;
    return 0;
}

- 미로찾기 축소판 (출발지에서 도착지까지 갈수있는지 확인하기)

#include<iostream>
using namespace std;
int map[4][4] = {
    0,0,0,0,
    1,0,1,0,
    1,0,1,0,
    0,0,0,0,
};
int visit[4][4] = { 1 };
int flag;
int direct[4][2] = { -1,0,1,0,0,-1,0,1 };
void abc(int y, int x)
{
    if (y == 3 && x == 3)
    {
        flag = 1;
        return;
    }
    for (int t = 0; t < 4; t++)
    {
        int dy = y + direct[t][0];
        int dx = x + direct[t][1];
        // 배열범위
        if (dy < 0 || dx < 0 || dy>3 || dx>3)continue;
        // 벽
        if (map[dy][dx] == 1)continue;
        // visit
        if (visit[dy][dx] == 1)continue;
        visit[dy][dx] = 1;    
        abc(dy, dx);
    }
}

int main()
{
    abc(0, 0);   // 시작 좌표값
    if (flag)cout << "도착가능";
    else cout << "도착 불가능";
    return 0;
}

- 취객의 빠른길찾기 (DFS + direct)

#include <iostream>

using namespace std;

int map[5][4] = {
	3,2,4,1,
	0,1,0,5,
	2,0,3,0,
	5,4,0,2,
	2,5,0,3,
};

int Max = 0;

void run(int now, int le, int sum) {
	if (le == 5) {
		if (Max < sum) Max = sum;
		return;
	}

	for (int i = 0; i < 3; i++) {
		int direct[3] = { -1,0,1 }; //행은 레벨과 같음, 열은 행기준 direct
		int dy = le;
		int dx = direct[i] + now;
		if (dx < 0 || dx >= 4) continue; //dy는 레벨임으로 따로 조건 안줘도 됨
		if (map[dy][dx] == 0)continue; //0은 갈수없는길임으로 패스
		run(dx, le + 1, sum + map[dy][dx]);
	}
}

int main() {

	for (int i = 0; i < 4; i++) { // 1~4열 각각 출발하는경우마다 경로의 합이 달라짐 
		run(i, 0, 0); //now level sum
	}

	cout << Max;

	return 0;
}

- 1~9중 4등까지의 합이 10이하가되는 경우는 몇번?

#include <iostream>

using namespace std;

int used[10];
int cnt = 0;

void run(int le, int sum) {

	if (sum > 10)return;

	if (le == 4) {
		cnt++;
		return;
	}

	for (int i = 1; i < 10; i++) {
		if (used[i] == 1)continue;
		used[i] = 1;
		run(le + 1, sum + i);
		used[i] = 0;
	}
}

int main() {
	
	run(0,0);

	cout << cnt;

	return 0;
}