알고리즘 스터디 26일차

1. 타겟넘버

1) 문제

문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예시

numbers target return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2

2) 문제 분석 및 풀이

1) 설계, 분석

모든 경우를 따지는 문제. 단 순서를 바꾸지 않는다고 했으니. DFS만으로 해결가능

2) 풀이

#include <string>
#include <vector>

using namespace std;
vector<int> gnumbers;
int gtarget;

int dfs(int value, int depth)
{
    int cnt = 0;
    if (depth == gnumbers.size())
    {
        if (value == gtarget) return 1;
        else return 0;
    }
    //-시작
    cnt += dfs(value - gnumbers[depth], depth+1);
    //+시작
    cnt += dfs(value + gnumbers[depth], depth+1);

    return cnt;
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    gnumbers = numbers;
    gtarget = target;

    answer = dfs(0,0);

    return answer;
}

2. 여행 경로

1) 문제

문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

tickets return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

2) 문제 분석 및 풀이

1) 설계, 분석

정점을 기준으로 탐색을 하는게 아니라, 티켓을 기준으로 탐색하는 문제

2) 풀이

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
vector<vector<string>> gtickets;
vector<bool> ticketVisited;
vector<string> answer;
int N;
bool dfs(string start, int depth)
{
    answer.push_back(start);
    if (depth > N) return true;
    for (int i=0; i<N; i++)
    {
        if (start != gtickets[i][0]) continue;

        if (ticketVisited[i]) continue;
        ticketVisited[i] = true;

        bool isdone = dfs(gtickets[i][1], depth+1);
        if (isdone) return true;
        ticketVisited[i] = false;
    }
    answer.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());

    gtickets = tickets;
    N = tickets.size();

    ticketVisited.resize(N,false);
    dfs("ICN", 1);
    return answer;
}

3. 주사위 윷놀이

1) 문제

2) 문제 분석 및 풀이

1) 설계, 분석

모든 경우를 탐색하는 문제. 말 4개에 대해서 백트래킹 + dfs로 완전 탐색을한다.
(파란색 칸의 경로처리를 어찌할지 몰라서 다른 코드를 참고했다)

2) 풀이

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <unordered_map>
#include <climits>

using namespace std;
vector<int> diceVec;
vector<int> pawnVec(4, 0);
//i번째 칸에서 갈 수 있는 칸
vector <int> nextMAP[33] = { 
	{1}, {2}, {3}, {4}, {5},				// 0 ~ 4
	{6, 21}, {7}, {8}, {9}, {10},			// 5 ~ 9
	{11,25}, {12}, {13}, {14}, {15},		// 10 ~ 14
	{16, 27}, {17}, {18}, {19}, {20},		// 15 ~ 19
	{32}, {22}, {23}, {24}, {30},			// 20 ~ 24
	{26}, {24}, {28}, {29}, {24},			// 25 ~ 29
	{31}, {20}, {32}						// 30 ~ 32
};

int scoreMAP[33]{
	0, 2, 4, 6, 8,				// 0~4
	10, 12, 14, 16, 18,			// 5~9
	20, 22, 24, 26, 28,			// 10 ~ 14
	30, 32, 34, 36, 38,			// 15 ~ 19
	40, 13, 16, 19, 25,			// 20 ~ 24
	22, 24, 28, 27, 26,			// 25 ~ 29
	30, 35, 0					// 30 ~ 32
};

int answer = 0;

void dfs(int sum, int depth)
{
    if (depth == 10)
    {
        answer = max(answer, sum);
        return;
    }

    for (int i=0; i<4; i++)
    {
        // 말 4개중에 하나 선택
        int iPawnCurPos = pawnVec[i];
        int nextCell;

        // 시작칸에 파란색 화살표가 있는지 확인
        if (nextMAP[iPawnCurPos].size() == 2)
        {
            nextCell = nextMAP[iPawnCurPos][1];
        }
        else
        {
            nextCell = nextMAP[iPawnCurPos][0];
        }

        // 주사위 눈 만큼 이동
        for (int j=1; j<diceVec[depth]; j++)
        {
            nextCell = nextMAP[nextCell][0];
        }

        // 이동할 칸에 이미 말이 있으면 끝
  		// 단 마지막칸은 제외
        bool found = false;
        for (int j=0; j<4; j++)
        {
            if (i==j) continue;
            if (pawnVec[j] == nextCell && nextCell!=32) found = true;
        }
        if (!found || nextCell == 32)
        {
            pawnVec[i] = nextCell;
            dfs(sum + scoreMAP[nextCell], depth+1);
            pawnVec[i] = iPawnCurPos;
        }
    }
}

int main()
{
    for (int i=0; i<10; i++)
    {
        int num;
        cin >> num;
        diceVec.push_back(num);
    }

    dfs(0,0);

    cout << answer << endl;
    return 0;
}

4. 벽 부수고 이동하기 2

1) 문제

2) 문제 분석 및 풀이

1) 설계, 분석

벽 부수고 이동하기의 심화버전, k개까지 부술 수 있다.
탐색을 할 때 상태를 저장하는게 포인트.

2) 풀이

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;
#define NMAX 1001
#define MMAX 1001

struct Pos
{
	int x;
	int y;
	int distance;
	int _breakCnt;

	bool operator==(Pos &operand)
	{
		return ((operand.x == x) && (operand.y == y));
	}

	bool operator!=(Pos &operand) { return !(*this == operand); }
};

int N, M, K;
int stage[NMAX][MMAX]; // 맵 정보
bool visited[NMAX][MMAX][11];

bool CanGo(int x, int y, const Pos &head, int &nb)
{
	if (x < 0 || x >= N || y < 0 || y >= M)
		return false;
	// 목표 지점이 벽이 아님
	if (stage[x][y] == 0 && !visited[x][y][head._breakCnt])
	{
        //현재 상태로 방문하지 않았으면 방문처리
		visited[x][y][head._breakCnt] = true;
		nb = head._breakCnt;
		return true;
	}
	// 목표 지점이 벽임
	else if (stage[x][y] == 1 && head._breakCnt < K && !visited[x][y][head._breakCnt+1])
	{
		// 현재까지 K번 미만으로 벽을 부쉈고
		// 현재보다 1개 더 부순 상태에서 이미 방문하지 않은 경우 (벽을 부수면 앞의 조건과 같은데 늦게방문한거니까)
		// 벽을 부숨
		visited[x][y][head._breakCnt + 1] = true;
		nb = head._breakCnt + 1;
		return true;
	}
	return false;
}

int BFS()
{
	queue<Pos> q;
	Pos EndPos { N - 1, M - 1 };
	Pos StartPos { 0, 0, 1, 0 };

	bool found = false;
	// 시작점 추가
	q.push(StartPos);
	visited[0][0][0] = true;

	while (true)
	{
		if (q.size() == 0)
			break;

		Pos posHead = q.front();
		q.pop();

		if (posHead == EndPos)
		{
			return posHead.distance;
		}

		// R D L U 순으로 탐색
		int dx[4] = { 0, 1, 0, -1 };
		int dy[4] = { 1, 0, -1, 0 };

		for (int i = 0; i < 4; i++)
		{
			int nx = posHead.x + dx[i];
			int ny = posHead.y + dy[i];
			int nb;

			if (CanGo(nx, ny, posHead, nb))
			{
				q.push(Pos { nx, ny, posHead.distance + 1, nb });
			}
		}
	}

	return -1;
}

int main()
{
	ios_base ::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < M; j++)
		{
			stage[i][j] = s[j] - '0';
		}
	}
	int res = BFS();
	cout << res << "\n";

    return 0;
}