저그유저의 프로그래밍

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

위키백과:

그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

이 외에도 홀수개의 사이클이 없어야 한다는데 이게 이해가 잘 안됐었는데 그림으로 다시 확인해보면

홀수 사이클에선 파랑 - 파랑 으로 같은 색끼리 연결이 될 수 밖에 없기 때문에 이분 그래프가 아니다.

DFS나 BFS를 통해 색을 칠하며 정점을 탐색하는 것이 중요한 문제였다.

코드에서는 DFS에서 탐색을 하면서, 이분 그래프 여부도 같이 체크해줬다.

color는 방문전에는 0으로 시작하고, 탐색 시 color % 2 + 1 을 통해 색을 반전시켜줬다.

color = 1인 경우 1 % 2 + 1 = 2

color = 2인 경우 2 % 2 + 1 = 1

memset도 필요한 부분까지만 리셋해주며 코드를 좀 더렵혀봤다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int color[20001];
bool isBipartiteGraph;

void DFS(vector<vector<int>>& list, int current, int nextColor)
{
	int size = list[current].size();

	for (int i = 0; i < size; ++i)
	{
		if (!isBipartiteGraph)
		{
			return;
		}

		int next = list[current][i];

		if (color[next] == 0)
		{
			color[next] = nextColor;
			DFS(list, next, nextColor % 2 + 1);
		}
		else if (color[current] == color[next])
		{
			isBipartiteGraph = false;
			return;
		}
	}
}

int main()
{
	int testCase;
	int v, e;
	int from, to;

	cin.tie(0);
	cin >> testCase;

	while (testCase--)
	{
		vector<vector<int>> list;
		isBipartiteGraph = true;

		cin >> v >> e;

		list.resize(v + 1);
		memset(color, 0, sizeof(int) * (v + 1));

		for (int i = 0; i < e; ++i)
		{
			cin >> from >> to;

			list[from].push_back(to);
			list[to].push_back(from);
		}

		for (int i = 1; i <= v; ++i)
		{
			if (color[i] == 0)
			{
				color[i] = 1;
			}

			DFS(list, i, color[i] % 2 + 1);
		}

		if (isBipartiteGraph)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
}

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

배열 인덱스에 해당하는 곳을 지그재그로 출력하는 문제이다.

1/1 1/2 1/3 1/4 ...

2/1 2/2 2/3 2/4 ...

3/1 3/2 3/3 3/4 ...

...    ...    ...   ...   ...

[1]      [2]       [3]      [4]      [5]      [6]      [7]

1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> 1/4 -> ...

식으로 진행이 된다.

규칙을 먼저 찾아보면

1. 최대 숫자가 1, 2, 3, 4 순서대로 증가한다.

ex)
 1 시작 => 1/1

 2 시작 => 1/2, 2/1

 3 시작 => 3/1, 2/2, 1/3

2. Ascending (오름차순 ex: 1 2 3 4) , Descending (내림차순 ex: 4 3 2 1)이 반복되는 형태로 되어있다.

2번 규칙 순서가 바뀌는 것을 제외하고 1번 규칙만을 놓고 나열을 해보면 아래와 같이 숫자가 나열 된다.

1/1

1/2 2/1

1/3 2/2 3/1

1/4 2/3 3/2 4/1

잘 보면

X / 최대 숫자

X + 1 / 최대 숫자 - 1

...

이런식으로 흘러가는 걸 알 수 있다.

이걸 이용해서

X - 최대 숫자 > 0 이면

   X = X - 최대숫자, 최대숫자 증가

X - 최대 숫자 <= 0 이면

   오름차순 or 내림차순 순서에 따라 X / 최대 숫자 - X + 1 또는 최대 숫자 - X + 1 / X

  를 출력해주기만 하면 된다. (이렇게 작성함)

#include <iostream>

using namespace std;

int main()
{
	int x;
	int num = 1;
	bool isAscending = true;

	cin >> x;

	while (true)
	{
		isAscending = !isAscending;

		if (x - num <= 0)
		{
			if (isAscending)
			{
				cout << x << "/" << num - x + 1 << endl;
			}
			else
			{
				cout << num - x + 1 << "/" << x << endl;
			}

			break;
		}

		x -= num;
		num++;
	}
}

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

SCC (Strongly Connected Component) 는 그래프 내에서 사이클을 이루는 각각의 그룹을 의미한다.

연결이 되어 있지 않아 1개인 경우도 하나의 그룹으로 취급한다.

문제가 어려워 접근 방법을 몰랐는데

아래 블로그에 SCC에 대해서 [코사라주 알고리즘]과 [타잔 알고리즘]에 대해서 잘 소개해주고 있다.

친절한 설명 덕분에 잘 이해할 수 있게 되었고 직접 실습하고 기억을 남긴다.

https://jason9319.tistory.com/98

개념을 간단히 정리해보면 이렇다.

[코사라주 알고리즘]

1. 입력에 대한 원본 그래프가 필요하다 (리스트 또는 배열)

2. 역방향 그래프가 필요하다. (입력에 대해서 역방향 ex)  원본이 1 -> 2 라면 2 -> 1로 저장

3. 방문여부 체크용 배열이 필요하다.

4. 스택이 필요하다. <- 이 부분은 벡터로 활용해도 된다. (dfs 함수 재사용을 위해 벡터로 사용해주었다.)

step

 1. 원본을 입력 받는다. 동시에 역방향 그래프도 만들어준다.

 2. 원본 그래프에 대한 dfs 를 통해 후위 순회 순서대로 스택에 정점 번호를 저장해준다. (트리의 후위 순회 개념)

 3. 스택에서 정점 번호를 하나씩 꺼내고 방문했는지 확인한다.

   (이미 탐색 o) pass

   (이미 탐색 x) 역방향 그래프로 다시 dfs 를 해본다. 그리고 해당 결과에 이용된 정점들을 저장해준다.

                    이 정점들이 하나의 사이클, 즉 그룹을 이루고 있는 것들이다.

 4. 문제에서 순서대로 출력하는 것을 원하기 때문에 sort를 해준다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int SIZE = 10001;

bool visited[SIZE];

void dfs(vector<vector<int>> &linkList, vector<int> &subVector, int vertex)
{
	int size = linkList[vertex].size();

	visited[vertex] = true;
	
	for (int i = 0; i < size; ++i)
	{
		int next = linkList[vertex][i];

		if (visited[next])
		{
			continue;
		}

		dfs(linkList, subVector, next);
	}
	
	subVector.push_back(vertex);
}

int main()
{
	vector<vector<int>> link;
	vector<vector<int>> reverseLink;
	vector<vector<int>> group;
	vector<int> arrayStack;
	vector<int> subGroup;

	int v, e;
	int from, to;

	cin.tie(0);
	cin >> v >> e;

	link.resize(v + 1);
	reverseLink.resize(v + 1);

	for (int i = 0; i < e; ++i)
	{
		cin >> from >> to;
	
		link[from].push_back(to);
		reverseLink[to].push_back(from);
	}

	for (int i = 1; i <= v; ++i)
	{
		if (!visited[i])
		{
			dfs(link, arrayStack, i);
		}
	}

	memset(visited, false, sizeof(visited));

	for (int i = arrayStack.size() - 1; i >= 0; --i)
	{
		int vertex = arrayStack[i];

		if (visited[vertex])
		{
			continue;
		}

		dfs(reverseLink, subGroup, vertex);
		
		sort(subGroup.begin(), subGroup.end());
		group.push_back(subGroup);
		
		subGroup.clear();
	}

	sort(group.begin(), group.end());
    
	cout << group.size() << endl;
	for (int i = 0; i < group.size(); ++i)
	{
		for (int j = 0; j < group[i].size(); ++j)
		{
			cout << group[i][j] << " ";
		}
		cout << "-1" << endl;
	}
}

[타잔 알고리즘]

타잔 알고리즘은 역방향 그래프가 필요없다. 대신에 그룹화가 되어있는지를 체크해줘야 한다.

1. 원본 그래프

2. 방문여부 배열

3. 그룹화여부 배열

4. 스택

step

 1. 원본을 입력 받는다.

 2. 방문하지 않은 정점부터 SCC 탐색을 시작해준다.

    현재 탐색 순서(ret)와 방문여부(visited)를 지정해준다.

    (이 부분을 통해 나중에 몇 번째부터 그룹화를 해줄지 정해주게 된다.)

    그리고 스택에 현재 방문한 정점을 저장한다.

 3. 현재 정점과 연결 된 정점을 찾아본다.

   3-1. 방문했었고 이미 SCC그룹이 확인된 곳)

          그냥 지나친다.

   3-2. 아직 방문하지 않은 곳)  ret = min ( ret, SCC(next) );

          해당 정점을 기준으로 SCC 탐색을 반복한다. 이 때 현재 탐색 순서의 갱신이 필요할 수 있다.

         다음 방문하는 곳에서 그룹의 기준이 될 곳을 만날 수 있기 때문에 현재 탐색 순서 (ret)을 더 작은 값으로

         갱신해줘야 한다.

   3-3. 방문했었고, 아직 SCC그룹화 되어있지 않은 곳)  ret = min( ret, visited[next] );

          현재 탐색 순서 (ret)와 해당 탐색 순서 (visited[next])를 비교하여 작은 곳을 기준으로 삼아준다. (ret을 더 작게) 

          이 부분이 어려웠다. 의미하는 것은 아래 그림으로..!

============================================================================

 1번 정점에서 탐색을 시작한다. ret = 1, visited[1] = 1이고 스택에 1을 넣어준다.

 이웃 노드로 미방문 노드 2번이 있다. 이제 SCC(2) 로 간다.

 ret = 2, visited[2] = 2로 시작하고 스택에 2를 넣어준다.

 "-" 는 이미 그룹화가 되어있기 때문에(방문도 되었기에) 더 이상 진행할 필요가 없다. 그냥 넘어가면 된다.

 2->1 은 연결이 되어있다. 1번은 이미 지나왔기 때문에 방문 상태이고 그룹화는 되어있지 않다.

1번과 2번은 그룹으로 묶일 수 있게 되는데, 가장 최초의 탐색 순서로 ret을 지정해준다. 이유는 이 ret을 통해

현재 탐색 지점 ~ 최초 탐색 지점 까지 스택에서 꺼내서 그룹으로 묶어주기 위해서이다! ( 스택 { 1 , 2(top) } )

 결과적으로 2번의 Ret = 1, Visited[2] = 2가 된다.

============================================================================

 4. 현재 Visited와 Ret이 동일한지를 확인한다. 동일하지 않다면 그냥 넘어가면 되고 (ret != visited[index])

   동일하다면 스택에서 현재 번호가 나올때까지 모두 꺼낸다. 이 정점들이 그룹화를 이루고 있는 곳이다.

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

using namespace std;

int order = 1;
bool isScc[10001];
int visited[10001];
vector<vector<int>> list;
vector<vector<int>> group;
stack<int> s;

int SCC(int index)
{ 
	int ret = visited[index] = order++;
	s.push(index);

	int size = list[index].size();
	for (int i = 0; i < size; ++i)
	{
		int next = list[index][i];

		if (visited[next] == 0)
		{
			ret = min(ret, SCC(next));
		}
		else if (!isScc[next])
		{
			ret = min(ret, visited[next]);
		}
	}

	if (ret == visited[index])
	{
		vector<int> subGroup;
		while (true)
		{
			int vertex = s.top();
			s.pop();

			subGroup.push_back(vertex);
			isScc[vertex] = true;

			if (vertex == index)
			{
				break;
			}
		}

		sort(subGroup.begin(), subGroup.end());
		group.push_back(subGroup);
	}

	return ret;
}

int main()
{
	int v, e, from, to;

	cin.tie(0);
	cin >> v >> e;

	list.resize(v + 1);
	for (int i = 0; i < e; ++i)
	{
		cin >> from >> to;
		list[from].push_back(to);
	}

	for (int i = 1; i <= v; ++i)
	{
		if (visited[i] > 0)
		{
			continue;
		}

		SCC(i);
	}

	sort(group.begin(), group.end());

	cout << group.size() << endl;
	for (int i = 0; i < group.size(); ++i)
	{
		for (int j = 0; j < group[i].size(); ++j)
		{
			cout << group[i][j] << " ";
		}
		cout << "-1" << endl;
	}
}

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

#include <iostream>

using namespace std;

int GetMin(int a, int b)
{
	return a < b ? a : b;
}

int BinarySearch(int n, int k)
{
	int left = 1, right = k;

	while (left < right)
	{
		int mid = (left + right) / 2;
		int count = 0;

		for (int i = 1; i <= n; ++i)
		{
			count += GetMin(mid / i, n);
		}

		if (count < k)
		{
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}

	return right;
}

int main()
{
	int n, k;
	cin >> n >> k;

	cout << BinarySearch(n, k) << endl;
}

다른 분들이 짠 코드를 봤는데 결국 똑같은 코드가 되어버렸다.

처음에 문제를 봤을 때 이걸 어떻게 이진탐색으로 푸는거지?? 생각이 들었지만 지금은 이해가 되었다.

문제는 이렇다.

2차원 n x n 크기의 배열 A가 있다. (모든 인덱스는 1부터 시작)

각 인덱스에 따라 [i][j] = i x j 의 값이 들어있다.

예를 들어

n = 3이면

[1][1] 1x1 = 1  [1][2] 1x2 = 2  [1][3] 1x3 = 3

[2][1] 2x1 = 2  [2][2] 2x2 = 4  [2][3] 2x3 = 6

[3][1] 3x1 = 3  [3][2] 3x2 = 6  [3][3] 3x3 = 9

이 배열을 B라는 1차원 오름차순 배열로 만든다.

B[1] = 1

B[2] = 2

B[3] = 2

B[4] = 3

B[5] = 3

B[6] = 4

B[7] = 6

B[8] = 6

B[9] = 9

이 중에서 k번째의 값은 무엇인가?

   k가 7이라면 B[7] = 6

위의 코드에서 핵심은 count를 세는 방법에 있다.

다시 한번 배열을 살펴보면

[1][1] 1x1 = 1  [1][2] 1x2 = 2  [1][3] 1x3 = 3        i = 1의 배수

[2][1] 2x1 = 2  [2][2] 2x2 = 4  [2][3] 2x3 = 6        i = 2의 배수

[3][1] 3x1 = 3  [3][2] 3x2 = 6  [3][3] 3x3 = 9        i = 3의 배수

즉 각 배수로 나누어봐서 그 결과가 내가 찾는 인덱스 값과 같다면 해당 숫자가 정답이 된다.

만약에 내가 B[4] (3)를 찾고 싶다면 위의 코드는 이렇게 동작이 된다.

left = 1, right = 4

mid = (1 + 4) / 2 = 2

for

i = 1   count += 2 / 1 (2)

i = 2   count += 2 / 2 (1)

i = 3   count += 2 / 3 (0)

count = 3으로 "2" 는 3번째 숫자란 의미가 된다.

4번째 숫자를 찾고 싶기 때문에

left = mid + 1을 해주고 다시 탐색을 해본다.

left = 3, right = 4

mid = (3 + 4) / 2 = 3

for

i = 1  count += 3 / 1 (3)

i = 2  count += 3 / 2 (1)

i = 3  count += 3 / 3 (1)

count = 5가 된다. 그러나 걱정할거 없다. 이미

B[3] = 2

B[4] = 3

B[5] = 3

으로 사잇값은 3으로 동일하기 때문이다.

추가적으로 GetMin(mid / i, n) 을 통해 더 작은 값으로 판별해주는데 예를 들어

6 x 6 배열에서

36번째를 찾게 된다면

left = 1, right = 36

mid = (1 + 36) / 2 = 18

i는 1일 때 18 / 1 = 18이 되어버린다.

n = 6 이므로 1x6 까지밖에 없는데 말이다.

수의 개수가 n을 넘어가버리면 모두 가능한 수로 취급하면 된다. mid / i, n 둘 중 작은 수를 더해주면 된다.

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

#include <stdio.h>
#include <string.h>

char n[10];
int result = -1;

void Swap(int a, int b)
{
    char temp = n[a];
    n[a] = n[b];
    n[b] = temp;
}

char GetMaxNum(int start, int length)
{
    char num = n[start];
    for (int i = start + 1; i < length; ++i)
    {
        if (num < n[i])
        {
            num = n[i];
        }
    }
    return num;
}

bool IsRightOrder(int length)
{
    for (int i = 1; i < length; ++i)
    {
        if (n[i - 1] < n[i])
        {
            return false;
        }
    }

    return true;
}

bool ExistSameNum(int length)
{
    for (int i = 1; i < length; ++i)
    {
        if (n[i - 1] == n[i])
        {
            return true;
        }
    }
    return false;
}

int GetMax(int a, int b)
{
    return a > b ? a : b;
}

int ArrayToNum(int length)
{
    int num = 0;
    for (int i = 0; i < length; ++i)
    {
        num = num * 10 + n[i] - '0';
    }
    return num;
}

void ChangeNumbers(int step, int k, int start, int length)
{
    if (step == k)
    {
        result = GetMax(result, ArrayToNum(length));
        return;
    }

    if (IsRightOrder(length))
    {
        if (!ExistSameNum(length) && (k - step) % 2 == 1)
        {
            Swap(length - 1, length - 2);
            result = GetMax(result, ArrayToNum(length));
            Swap(length - 1, length - 2);
        }
        else
        {
            result = GetMax(result, ArrayToNum(length));
        }

        return;
    }

    if (start + 2 == length)
    {
        Swap(start, start + 1);
        ChangeNumbers(step + 1, k, start, length);
        Swap(start, start + 1);
    }
    else
    {
        char maxNum = GetMaxNum(start, length);

        if (n[start] == maxNum)
        {
            ChangeNumbers(step, k, start + 1, length);
        }

        for (int i = start + 1; i < length; ++i)
        {
            if (n[i] == maxNum)
            {
                Swap(start, i);
                ChangeNumbers(step + 1, k, start + 1, length);
                Swap(start, i);
            }
        }
    }
}

int main()
{
    int k;
    int length;

    scanf("%s %d", n, &k);
    length = strlen(n);

    if (length <= 1 || (length == 2 && n[1] == '0'))
    {
        printf("-1\n");
        return 0;
    }

    ChangeNumbers(0, k, 0, length);
    printf("%d\n", result);
}

처음에 굉장히 쉬운줄 알았는데 예상치 못한 테스트 케이스가 많았던 문제였다.

처음부터 알아낸 조건과 삽질하며 알아낸 조건들이 있다. 정리를 해보면

1. 1개면 교환이 불가능하다. (-1 출력)

2. 2개일 때 뒤에 0이 있다면 교환이 불가능하다. (-1 출력)

    (여기까지 미리 1~9, 10, 20, 30 ... 90 까지의 숫자는 걸러준다.)

3. 당연하게도 무조건 가장 큰 수가 맨 앞으로 가면 좋다! 그러나 고려해야 될 조건이 두 가지 있다.

  3-1. 가장 큰 수가 "맨 앞에만" 있다.

        ex) 930 => 9를 스킵하고 30에 대해서만 교환을 해주면 된다.

             97  => 2개이기 때문에 스킵이 불가능하다. 무조건 교환해줘야 된다.

  3-2. 가장 큰 수가 "여러개" 일 경우이다.

        (처음에 가장 뒤에놈을 앞으로 옮겨줬는데 아래 테스트 케이스 중 그러면 안되는 것이 있다.)

        ex) 9989 1 => 9998

             3699 2 => 9963

             6399 2 => 9963 (이놈)

 4. 이미 차례대로 정렬되어 있다면 마지막 2개만 교환해주거나 교환해줄 필요가 없어진다.

        ex) 9876 1 => 9867,    9876 2 => 9876

             9987 x => (맨 앞의 99만 계속 교환해주면 끝) 9987

3번 조건의 가장 큰 수가 여러개 있는 경우에 탐색의 분기점이 생긴다.

그래서 Swap 이 후 다시 Swap을 통해 기존의 배열을 유지시키며 탐색을 하게 만들었다.

코드를 보면 나처럼 멍청한 사람이 코딩하면 이렇게 코드가 길어지고 시행착오를 겪게 되며 시간을

많이 쓰게 된다는 것을 다시 느끼게 된다.. ㅠㅠ

다른 사람이 잘 작성한 코드도 보면서 더 쉽고 간결하게 짤 수 있는 방법도 보고 이해해야 된다!

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

#include <stdio.h>

long long BinarySearch(long long start, long long end, long long x, long long y, long long z)
{
	long long mid, z2;
	long long result = -1LL;

	while (start < end)
	{
		mid = (start + end) / 2LL;
		z2 = (y + mid) * 100LL / (x + mid);

		if (z2 <= z)
		{
			start = mid + 1LL;
		}
		else if (z < z2)
		{
			end = mid;
			result = end;
		}
	}

	return result;
}

int main()
{
	long long x, y, z, result;

	scanf("%lld %lld", &x, &y);
	z = y * 100LL / x;

	result = BinarySearch(0, x + 1, x, y, z);
	printf("%lld\n", result);
}

이진 탐색을 활용하여 결과를 구할 수 있었다.

퍼센트로 나타내기 위해선 소수점 2자리만 필요하기 때문에 100판 중 40판을 이겼다면

40 * 100 / 100 으로 정수형이기 때문에 소수점을 제외하고 나타낼 수 있다. ( 4000 / 100 = 40 )

이 때 int형은 오버플로우가 발생할 수 있기에 모두 long long 형으로 설정해주었다.

계산 중 실수했던 부분이 게임을 이길수록 전체 판수도 함께 증가해야 된다는 것이었다.

새로운 승률 z2 = (기존 승리 + 추가 승리) * 100 / (전체 판수 + 추가 승리)

BinarySearch 매개변수인 long long end 값은 전체 판수 + 1 (x + 1)로 해주었다.

이 값이 현재 로직에서 탐색의 최대 범위이다.

전체 판수 : 1000000000 (10억)
이긴 판수 :  980000000 (9억 8천)

위의 경우는 총 10억판을 이기면 승률이 98%에서 99%로 올라가게 된다. (1980000000 / 2000000000)

근데 이진 탐색 로직을 보면 z < z2 (기존 승률 < 새로운 승률) 인 경우에만 result를 갱신하게 된다.

end 값이 줄어들어야 result가 갱신이 되는데 end값이 곧 정답이기에 작아질 수가 없기 때문이다.

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

#include <stdio.h>
#include <stdlib.h> //system("pause") 쓰기 위한 라이브러리

char map[10000][501]; //char 배열은 마지막 null 문자 들어가야되서 크기 + 1
int used[10000][500];
int dirR[3] = { -1, 0, 1 };

int maxRow, maxCol;
int result;
bool finished;

//현재 진행 상태를 볼 수 있게 만든 함수
void PrintState()
{
	printf("\n");
	for (int i = 0; i < maxRow; ++i)
	{
		for (int j = 0; j < maxCol; ++j)
		{
			if (map[i][j] == 'x')
			{
				printf("x");
				continue;
			}
			printf("%d", used[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	system("pause"); // 키를 누를 때까지 멈춤
}

void DFS(int row, int col, int num) //Depth First Search
{
	//PrintState(); //dfs 탐색 순서를 보고 싶다면 주석 제거

	if (col == maxCol - 1)
	{
		result++;
		finished = true;
		return;
	}

	int nextCol = col + 1;
    
	for (int i = 0; !finished && i < 3; ++i)
	{
		int nextRow = row + dirR[i];

		if (0 <= nextRow && nextRow < maxRow &&
			map[nextRow][nextCol] == '.' &&
			used[nextRow][nextCol] == 0)
		{
			used[nextRow][nextCol] = num;
			DFS(nextRow, nextCol, num);
		}
	}
}

int main()
{
	scanf("%d %d", &maxRow, &maxCol);

	for (int i = 0; i < maxRow; ++i)
	{
		scanf("%s", map[i]);
	}

	for (int i = 0; i < maxRow; ++i)
	{
		finished = false;
		used[i][0] = i + 1;

		DFS(i, 0, i + 1);
	}

	PrintState(); //탐색 완료 된 형태 출력
	printf("%d\n", result);
}

깊이 우선 탐색이 필요한 문제였다.

그리고 탐색이 성공하면 기존의 탐색도 반드시 종료시켜야 된다.

이걸 안해주면 다음과 같은 상황이 발생하게 된다..

지 혼자 모든 곳을 다 점령해버린다.

ex) 4x4

   1111

   xx11

   xxx1

   xxxx

이를 위해 전역변수로 bool finished를 선언해주었고,

탐색 전에 finished = false,

탐색이 성공하면 finished를 true로 변경해준다.

DFS for문의 조건이 finished == false && i < 3 으로 되어있기에

한 번이라도 마지막 지역에 도착했다면 다른 탐색을 하지 않을 수 있게 된다.

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

#include <cstdio>
#include <vector>

using namespace std;

typedef struct Horse
{
	int row, col, dir;
	bool isBottom;
}Horse;

const int SIZE = 12;

vector<int> over[11];
Horse horse[11];

int map[SIZE][SIZE];
int unit[SIZE][SIZE];

int dirR[4] = { 0, 0, -1, 1 };
int dirC[4] = { 1, -1, 0, 0 };
int n;

int ReverseOrder(int index)
{
	vector<int> v = over[index];
	int size = v.size();

	if (size <= 1) //위에 쌓인게 없으면 그대로 둔다.
	{
		return index;
	}

	horse[index].isBottom = false;
	int row = horse[index].row;
	int col = horse[index].col;

	for (int i = 0; i < size / 2; ++i)
	{
		int temp = v[i];
		v[i] = v[size - 1 - i];
		v[size - 1 - i] = temp;
	}

	int newIndex = v[0]; //새로운 맨 밑이 탄생하였다.

	over[newIndex] = v;  //새로운 밑으로 말들 배치를 저장해주고,
	over[index].clear(); //기존 것은 제거해준다.

	horse[newIndex].isBottom = true; //새로운 말이 맨 밑이 되었고
	unit[row][col] = v[newIndex];    //현재 unit도 새로운 말 인덱스가 저장된다.

	return newIndex;   //기준 인덱스가 바뀌어야 된다.
}

void TurnAroundDirection(int index)
{
	int dir = horse[index].dir;
	dir = dir / 2 * 2 + (dir + 1) % 2;
	horse[index].dir = dir;
}

bool IsOutOfBound(int row, int col)
{
	return row < 0 || n <= row || col < 0 || n <= col;
}

bool Move(int index, int preRow, int preCol, int newRow, int newCol)
{
	int size = over[index].size();
	int bottom = unit[newRow][newCol];

	unit[preRow][preCol] = 0; //이동 전 기존 좌표는 비워준다.

	for (int i = 0; i < size; ++i) //위에 있는 말들도 함께 이동시킨다.
	{
		int idx = over[index][i];
		horse[idx].row = newRow;
		horse[idx].col = newCol;
	}

	if (bottom != 0) //이동하는 곳에 말이 있다면?
	{
		horse[index].isBottom = false;

		//bottom 벡터 리스트 맨 뒤에 이동 된 index 벡터 리스트를 추가하는 작업이다.
		over[bottom].insert(over[bottom].end(), over[index].begin(), over[index].end());
		over[index].clear();

		if (over[bottom].size() >= 4) //이동 후 말이 4마리 이상이면 게임 오버
		{
			return true;
		}
	}
	else //말이 없으면 그냥 점령한다.
	{
		unit[newRow][newCol] = index;
	}

	return false;
}

bool ProcessFromColor(int index, int step)
{
	Horse h = horse[index];
	
	int d = h.dir;
	int newRow = h.row + dirR[d];
	int newCol = h.col + dirC[d];

	if (IsOutOfBound(newRow, newCol))
	{
		if (step == 0)
		{
			TurnAroundDirection(index);
			return ProcessFromColor(index, step + 1);
		}
		else
		{
			return false;
		}
	}

	switch (map[newRow][newCol])
	{
		case 1:

			index = ReverseOrder(index);
			return Move(index, h.row, h.col, newRow, newCol);

		case 2:

			if (step == 0)
			{
				TurnAroundDirection(index);
				return ProcessFromColor(index, step + 1);
			}
			
			return false;
		default:

			return Move(index, h.row, h.col, newRow, newCol);
	}

	return false;
}

int main()
{
	int row, col, dir;
	int k;
	int moved = 0;
	
	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			scanf("%d", &map[i][j]);
		}
	}

	for (int i = 1; i <= k; ++i) //말 번호는 1~k까지 쓸거지만
	{
		//row, col은 0, 0부터, dir는 0,1,2,3 으로 쓸거라 감소 시켜준다.
		scanf("%d %d %d", &row, &col, &dir);
		row--;
		col--;
		dir--;

		Horse h;
		h.row = row;
		h.col = col;
		h.dir = dir;
		h.isBottom = true;

		horse[i] = h; //말 정보를 등록하고
		unit[row][col] = i; //맵에도 말을 등록해준다.
		over[i].push_back(i); //리스트에는 자신을 먼저 등록해준다.
	}

	while (moved < 1000)
	{
		moved++;

		for (int i = 1; i <= k; ++i)
		{
			if (horse[i].isBottom == false)
			{
				continue;
			}

			bool isFinish = ProcessFromColor(i, 0);
			if (isFinish)
			{
				printf("%d\n", moved);
				return 0;
			}
		}
	}

	printf("-1\n");
	return 0;
}

오랜만에 문제를 하나 풀어봤는데, 머리속으론 로직이 정리되었는데 막상 짜니깐 오류가 생기고..

문제를 잘 못 이해한 부분때문에 이상한 답이 나오며 고생한 문제였다.

문제를 정리하면

n x n 맵에 하얀색(0), 빨간색(1), 파란색(2) 의 칸들이 존재하고

k개의 말들이 놓여있으며 말들은 방향을 갖고 있고, 해당 방향으로만 움직일 수 있다.

말들은 작은 숫자 순서대로 움직이고, 다른 말을 만나면 이동한 말(들)은 그 위에 쌓이게 되며

"가장 밑에 있는 말만 움직일 수 있게 된다."

하얀색 칸은 그냥 이동, (이동 시 해당 칸에 이미 말이 존재하면 해당 말 위에 올린다.)

빨간색 칸은 이동하기 전에 1,2,3 순서라면 3,2,1 순서로 변경하여 이동,

파란색 칸은 방향을 뒤로 바꾼 후 갈 수 있다면 이동, 불가능하다면 이동하지 않는다.

위의 빨간색 조건 때문에 이상한 답이 나왔었는데, 1턴에 모든 말들이 이동할 수 있는지 계속 체크해줘야 한다.

만약 (맨 밑)1, 2로 이루어진 말이 있는데 이 말이 빨간 칸에 가게 되면

2, 1로 바뀌게 된다. 그리고 2번 말이 이동할 수 있게 되며 이것이 1턴에 이루어지는 일들이다. 아래는 예제..

그렇게 이 조건을 몰라서 왜 안돼지?? 뻘짓을 하고 말았다고 한다..

코드를 설명해보면

우선 맵의 상태를 저장할 map[size][size] 배열과

말들의 위치를 저장할 unit[size][size] 로 따로 관리해주고 있다.

unit은 말의 번호를 저장해두고,

말들에 대해선 horse 배열을 통해 현재 위치 (row, col), 방향, 맨 밑에 있는지를 알아 볼 수 있다.

(사실 체스 말인데.. 그냥 영어 말로함;)

unit[1][1] = 1 이라면

horse[1] = { row = 1, col = 1, dir = 어떤 방향, isBottom = true }

(벡터 리스트) over[1] = { 1, 위에 있는 말들 없으면 끝 } 

식으로 해당 인덱스를 대입해서 판별하게 해두었다.

vector<int> over[11] 는 위에 쌓이는 말들을 저장하기 위한 리스트로 초기 상태는 자신의 번호만 들어가있다.

ReverseOrder 또는 Move 시에 다른 말위에 올라탈 수 있다면 해당 리스트가 복사되는 형태이다.

ProcessFromColor 로직은 길긴한데.. 이렇게 생겼다.

1. 방향에 맞게 새로운 좌표를 지정 (d, newRow, newCol 설정)

2. 해당 좌표가 IsOutOfBound 라면 방향을 전환 후 이동할 수 있는지 다시 해본다.

(재귀 함수를 이용했는데 step이 0이 아니라면 이미 한번 방향을 돌린 것이고, 그래도 이동이 안되면 가만있는다.)

3. 이동한 곳의 map 정보 판별 ( switch (map[newRow][newCol] )

 3-1. (빨간 칸) ReverseOrder를 통해 뒤집어 주고, 새로운 맨 밑이 현재 인덱스로 설정하게 해주었다.

   이 함수에서 unit[row][col] 에 대한 말 번호, 맨 밑에 있던 말의 isBottom, 새로운 맨 밑이 된 말의 isBottom

   초기화가 굉장히 중요하다. 순서 바꾸는 건 for에 있음.

 3-2. (파란 칸) 방향 전환 후 이동인데, 이미 방향을 바꿨던 경우 (step > 0) 라면 그냥 가만있으면 된다.

 3-3. (하얀 칸) 이동한다. 이동 시 이동할 unit 배열을 통해 말이 있는지 없는지 판별한다.

                   기존 말이 없다면 이동한 말이 해당 좌표에 등록되면 되고,

                   기존 말이 있다면 그 말의 맨 위로 올려버리고 운명을 함께 하면 되겠다.

사실 부족한 코드지만 글을 쓰고, 정리하다보면 좀 더 나아지지 않을까 하는 생각으로 올려봅니다.

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

#include <stdio.h>

bool CrossCheck(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
    //중심점을 구하고 해당 점으로부터의 방향을 외적을 이용하여 찾아낸다.
    int baseX = ax1 - ax2;
    int baseY = ay1 - ay2;
    int x1 = bx1 - ax2;
    int x2 = bx2 - ax2;
    int y1 = by1 - ay2;
    int y2 = by2 - ay2;

    //백만 * 백만이 될 수 있어 정수형은 오버플로우 될 수 있다.
    long long cross1 = (long long)baseX * y1 - (long long)baseY * x1;
    long long cross2 = (long long)baseX * y2 - (long long)baseY * x2;

    if (cross1 == 0 || cross2 == 0) //같은 위치에 점이 있는 경우!
    {
        return 0; //교차로 할거면 1, 여기선 아니라고 해두었다.
    }

    if ((cross1 > 0 && cross2 > 0) ||
        (cross1 < 0 && cross2 < 0))   //중심점을 기준으로 양쪽이 같은 방향이면 교차x
    {
        return 0;
    }

    return 1;
}

int main()
{
    int ax1, ax2, ay1, ay2, bx1, bx2, by1, by2;
    int cross;
    
    scanf("%d %d %d %d", &ax1, &ay1, &ax2, &ay2);
    scanf("%d %d %d %d", &bx1, &by1, &bx2, &by2);

    cross = CrossCheck(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2);
    if (cross > 0) //성공하면 중심점을 바꿔서 한번 더 해본다.
    {
        cross = CrossCheck(bx1, by1, bx2, by2, ax1, ay1, ax2, ay2);
    }

    printf("%d\n", cross);
}

수학 관련된 문제..

벡터의 외적을 통해 방향을 알아내는 식으로 작성된 코드이다.

외적은 다음과 같은 행렬의 여인수(cofactor) 전개를 통해서 구할 수 있다.

아래처럼 일단 외적 계산을 위한 행렬을 배치해보자.

E1 = (1, 0, 0), E2 = (0, 1, 0), E3 = (0, 0, 1)

E1 E2 E3

x1 y1 z1

x2 y2 z2

2차원 공간이기 때문에 z1과 z2는 무조건 0이다!

그렇기 때문에 행렬식을 전개해보면 다음과 같이 된다.

 E1 * ( y1 * z2(0) - z1(0) * y2 ) = 0

-E2 * ( x1 * z2(0) - z1(0) * x2 ) = 0

 E3 * ( x1 * y2 - y1 * x2 ) = ??

즉 x1 * y2 - y1 * x2 계산을 통해 외적을 구할 수 있게 된다.

중심 선을 기준으로 오른쪽에 위치하면 마이너스가 나오게 되고,

왼쪽에 위치하면 플러스가 나오고 겹쳐 있다면 0이 나온다.

확인을 해보도록 하자!

위의 CrossCheck 코드를 보면

먼저 baseX, baseY 를 구하고 있다. 어느 지점을 기준으로 왼쪽 오른쪽을 판별할지를 결정하는 것이고,

특정한 점을 기준으로 좌표를 계산해주고 있다. (코드는 (3, 3) ax2, ay2 를 기준으로 삼고 있다.)

위의 그림의 경우는 (3, 3)이 중심이 된다고 가정하면

(1, 1) => (1, 1) - (3, 3) = (-2, -2)

(3, 5) => (3, 5) - (3, 3) = (0, 2)

(4, 3) => (4, 3) - (3, 3) = (1, 0)

이 된다. 이러한 그림이 되는 것이고, 중심점인 빨강 선을 기준으로 외적을 구한다.

0, 2에 대해서 외적을 구해보면

-2 -2

0  2    ==>  (-2 * 2) - (-2 * 0) = -4

음수값이 나온다. 즉 시계 방향(오른쪽)에 위치하고 있다.

0, 1에 대해서 외적을 구해보면

-2 -2

1  0     ==>  (-2 * 0) - (-2 * 1) = 2

양수값이 나오며 시계 반대방향(왼쪽)에 위치하고 있다고 판별이 된다.

우선 선분이 교차할 가능성이 생겨있게 된다. 교차할 수 없는 경우는

모두 양수 또는 음수가 나온 경우이다. (cross1 > 0 && cross2 > 0) || (cross1 < 0 && cross2 < 0)

빨간 선을 기준으로 판별한 결과 교차할 수 있다고 나왔다.

이번엔 파란 선을 기준으로 다시 판별을 해줘야 한다.

마찬가지로 기준점을 하나 잡아 준다. 위의 코드에선 a와 b에 대해서 순서가 바뀐 것을 확인할 수 있다.

(기준 점은 빨간 선, 파란 선을 구성하는 어느 점을 선택하든 결과는 똑같다!! <- 이걸 확인해보고 싶었다 ㅎㅎ)

파란선의 방향은 아래쪽이고.. 이러한 경우는 외적 결과가 오른쪽에 2개가 있다고 나올 것이므로

두 개의 선분은 교차하지 않는다. 파란 선을 기준으로도 왼쪽, 오른쪽이 나온다면 두 선분은

교차하게 된다. 설명을 잘 못해서 너무 길어졌네.. 어쨋든 나중에도 기억하도록!!

www.acmicpc.net/problem/17406

#include <vector>
#include <cstdio>

using namespace std;

typedef struct Oper
{
    int row, col, start;
}Oper;

int minValue = 987654321;
int n, m;

int min(int a, int b)
{
    return a < b ? a : b; //a가 b 보다 작으면 리턴 a, 아니면 리턴 b
}

//memset을 써도 된다.
void CopyArray(int copyArray[50][50], int arr[50][50])
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            copyArray[i][j] = arr[i][j];
        }
    }
}

void RotateRight(int arr[50][50], int copyArray[50][50], int r, int c, int s)
{
    if (s == 0)
    {
        return;
    }
    
    int up = r - s;
    int down = r + s;
    int left = c - s;
    intt right = c + s;

    for (int i = left + 1; i <= right; ++i)
    {
        copyArray[up][i] = arr[up][i - 1];
    }

    for (int i = up + 1; i <= down; ++i)
    {
        copyArray[i][right] = arr[i - 1][right];
    }

    for (int i = right - 1; i >= left; --i)
    {
        copyArray[down][i] = arr[down][i + 1];
    }

    for (int i = down - 1; i >= up; --i)
    {
        copyArray[i][left] = arr[i + 1][left];
    }

    //s를 줄여 점점 줄여가며 안쪽도 회전시켜준다.
    RotateRight(arr, copyArray, r, c, s - 1);
}

void RotateArray(int arr[50][50], vector<Oper>& v, vector<bool> &usedCheck, int needUse)
{
    if (needUse == 0) //모든 회전을 다 했다면
    {
        //전체 행 각각 합을 구하고 정답을 갱신한다.
        for (int i = 0; i < n; ++i)
        {
            int sum = 0;
            for (int j = 0; j < m; ++j)
            {
                sum += arr[i][j];
            }
            minValue = min(minValue, sum);
        }
        return;
    }

    int copyArray[50][50];
    int size = usedCheck.size();
    for (int i = 0; i < size; ++i)
    {
        if (usedCheck[i]) //이미 쓴 회전은 넘어간다.
        {
            continue;
        }

        usedCheck[i] = true; //회전 체크
		
        int r = v[i].row;
        int c = v[i].col;
        int s = v[i].start;

        CopyArray(copyArray, arr); //회전을 위해 배열 복사
        RotateRight(arr, copyArray, r, c, s); //오른쪽 회전을 한다.
        RotateArray(copyArray, v, usedCheck, needUse - 1); //다음 회전을 하러 간다.
		
        usedCheck[i] = false; //회전 체크 해제
    }
}

int main()
{
    vector<Oper> v;
    vector<bool> usedCheck;
    int arr[50][50] = { 0 };
    int k, r, c, s;

    scanf("%d %d %d", &n, &m, &k);
    usedCheck.resize(k);

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            scanf("%d", &arr[i][j]);
        }
    }

    for (int i = 0; i < k; ++i)
    {
        scanf("%d %d %d", &r, &c, &s);
        r--; //0부터 시작하는 배열을 쓸거기 때문에 1씩 줄여준다.
        c--; //위와 마찬가지

        v.push_back({ r, c, s });
    }

    RotateArray(arr, v, usedCheck, k); //돌린다.

    printf("%d\n", minValue);
}

문제를 간단히 정리해보면 n x m 배열을 행, 열 (r, c) 축을 기준으로 s 크기만큼의 영역만 돌리고,

각 행별로의 숫자들의 합이 최소가 되는 값을 찾는 문제이다.

이 때 r, c, s 는 k개까지 입력을 받고, 모든 회전을 다 해봐야된다.

만약 회전의 방법이 3가지라면

1 2 3

  3 2

2 1 3

  3 1

3 1 2

  2 3

( 3! = 6 ) 개 만큼의 모든 상황들을 시뮬레이션 해봐야 한다. 최대 ( 6! = 6x5x4x3x2x1 = 720 ) 가지 방법이 될 수 있다.

문제는 배열 돌리기 (해당 좌표에 대해서만) + 욕심쟁이 방법 (=브루트 포스), 두 가지를 통해 해결해야 된다.

가장 중요한 배열 돌리기에 대해서 살펴보면

              (시계 방향으로 회전)

1 2 3        4 1 2

4 5 6  =>  7 5 3

7 8 9        8 9 6

1칸씩 밀리는 방법이다.

배열의 주소를 이용하여 *( *(arr + i) + j) 와 같은 방법으로도 해결해 볼 수 있는 것 같지만, 복잡할거 같아 지금은 넘어가고, 직관적으로 풀어나가는 것이 좋을거라 생각 된다.

먼저 A 배열을 복사할 새로운 B 배열이 필요하고 

      1 2 3         x x x

A = 4 5 6    B = x x x

      7 8 9         x x x

다음과 같은 방법으로 배열을 돌릴 수 있다. 오른쪽, 아래, 왼쪽, 위 순서로 채워나갈 수 있다.

오른쪽으로 먼저 채운다. B는 아래와 같은 상태가 된다.

       x 1 2

B =  x x x

       x x x

for ( int i = left + 1; i <= right; ++i )

   B[ up ][ i ] = A[ up ][ i - 1 ];

즉 up = 0, left = 0, right = 2라면

  B[0][1] = A[0][0] (1)

  B[0][2] = A[0][1] (2)

가 된다. 다음으로 아래쪽으로 채우게 된다면?

       x 1 2

B =  x x 3

       x x 4

for ( int i = up + 1; i <= down; ++i )

   B[ i ][ right ] = A[ i - 1 ][ right];

왼쪽으로 채우면

       x 1 2

B =  x x 3

       6 5 4

(가장 오른쪽 - 1 에서 왼쪽까지 가기때문에 마이너스가 된다. 물론 플러스로 구현해도 상관없다.)

for ( int i = right - 1; i >= left; --i )

   B[ down ][ i ] = A[ down ][ i + 1]; 

마지막으로 위로 채우면

       8 1 2

B =  7 x 3

       6 5 4

for ( int i = down - 1; i >= up; --i )

   B[ i ][ left ] = A[ i + 1][ left ];

이런식으로 채워지게 된다. 먼저 이 회전에 대해서 이해하고, 나머지는 반복적인 재귀로 처리할 것!

분명히 나중에 또 까먹겠지.. ㅠㅠ