재시민

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

문제 설명

0으로 이루어진 바다위에 떠있는 1로 이루어진 섬.

섬끼리 다리를 지으려고 하는데 가장 짧은 다리를 구하자.

인사이트

섬들 중 어느 섬이든 간에 가장 짧은 다리를 만드는 경우를 출력하면 된다.

1. 전체 BFS 순회를 통해 몇 개의 섬이 있으며 지도에 있는 1이 몇번째 섬에 부분에 해당하는지 파악
2. 지도를 이중 for loop를 통해 지도 값이 1 인 칸에 대하여 주위 네 개의 면 중 0이 있다면 큐에 넣는다.
   1. 큐에 들어온 좌표를 기준으로 BFS 를 실행
   2. 주위 네 개의 면 중 하나가 0 이면 큐에 push
   3. 주위 네 개의 면 중 하나가 1 이고 다른 섬이면 정답 벡터의 담기
      1. 시작 좌표, 끝 좌표를 이용해 |끝좌표 - 시작좌표| - 1 값을 구해 최소 다리 길이를 구함
3. 이중 for loop 가 끝나면 정답 벡터의 최솟값을 출력

정답 코드

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

using namespace std;

int N, M;

int land[101][101];
int land_idx[101][101];
bool visited[101][101];
bool visited_idx[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int> ans;
    cin >> N;
    //초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> land[i][j];
        }
    }

    //2차원 배열을 순회하면서 땅이 몇개인지 파악하고 각 행렬의 1이 속하는 땅의 번호를 기입
    int idx = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited_idx[i][j])continue;
            if (land[i][j] != 1)continue;
            queue<pair<int, int>> q;
            q.push(make_pair(i, j));
            visited_idx[i][j] = true;
            idx++;
            land_idx[i][j] = idx;

            while (!q.empty()) {
                int y = q.front().first;
                int x = q.front().second;

                q.pop();

                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                    if (visited_idx[ny][nx])continue;
                    if (land[ny][nx] == 0)continue;
                    q.push(make_pair(ny, nx));
                    visited_idx[ny][nx] = true;
                    land_idx[ny][nx] = idx;
                }
            }
        }
    }


    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j])continue;
            if (land[i][j] != 1)continue;

            queue<pair<int, int>> q;
            //주변에 0이 있는 1인 시작점 찾아서 큐에 넣기
            bool check = false;
            for (int k = 0; k < 4; k++) {
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                if (land[ny][nx] == 0) {
                    if (land_idx[ny][nx] != land_idx[i][j])
                    {
                        check = true;
                    }
                }
                else {
                    continue;
                }
            }
            //4면 중 하나라도 0이면 큐에 담기
            if (check) {
                q.push(make_pair(i, j));
                visited[i][j] = true;
            } 
            //BFS
            while (!q.empty()) {
                int y = q.front().first;
                int x = q.front().second;

                q.pop();

                bool check = false;
                for (int k = 0; k < 4; k++) {
                    int ny = y + dy[k];
                    int nx = x + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;
                    if (visited[ny][nx]) continue;
                    //4면 중 하나가 0 이면 큐에 푸시
                    if (land[ny][nx] == 0) {
                        if (land_idx[ny][nx] != land_idx[i][j])
                        {
                            q.push(make_pair(ny, nx));
                            visited[ny][nx] = true;
                        }
                    //4면 중 하나가 1이면 정답 벡터에 푸시
                    }else if (land[ny][nx] == 1) {
                        if (land_idx[ny][nx] != land_idx[i][j]) {
                            ans.push_back(abs(ny - i) - 1 + abs(nx - j));
                            break;
                        }
                    }

                }
            }
            //재탐색을 위한 방문 초기화
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(land[i][j] == 0)visited[i][j] = 0;
                }
            }

        }
    }

    cout << *min_element(ans.begin(), ans.end());
}

www.acmicpc.net/problem/1018

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
	int Col; int Row;
	cin >> Col >> Row;

	vector<char> chess(51,0);
	vector<vector<char>> chessSpace(51,vector<char>(51,0));
	vector<char> chess1(51, 0);
	vector<vector<char>> chessSpace1(51, vector<char>(51, 0));

	vector<char> compare(51, 0);
	vector<vector<char>> chessCompare(51, vector<char>(51, 0));
	int i, j;
	for (i = 0;i < 8;i++) {
		for (j = 0;j < 8;j++) {
			if (i + j == 0 || (i + j) % 2 == 0) {// 0 이거나 2의 배수
				chessSpace[i][j] = 'W';
				chessSpace1[i][j] = 'B';
			}
			else {
				chessSpace[i][j] = 'B';
				chessSpace1[i][j] = 'W';
			}
		}
	}
	for (i = 0;i < Col;i++) {
		for (j = 0;j < Row;j++) {
			char A;
			cin >> A;
			chessCompare[i][j] = A;
		}
	}
	int count = 0;
	int count1 = 0;
	int ai, aj;
	
	vector<int> counter;
	for (ai = 0;ai <= Col - 8;ai++) {
		for (aj = 0;aj <= Row - 8;aj++) {
			int bi = 0; int bj = 0;
			for (i = ai;i < ai + 8;i++) {
				for (j = aj;j < aj + 8;j++) {
					if (chessSpace[bi][bj] != chessCompare[i][j]) {
						count++;
					}
					if (chessSpace1[bi][bj] != chessCompare[i][j]) count1++;
					if (bj <= 8)bj++;
				}if(bi<=8)bi++;
				 bj = 0;
			}counter.push_back(count);
			counter.push_back(count1);
			count = 0;
			count1 = 0;
			 bi = 0; 
		}
	}
	int min = *min_element(counter.begin(), counter.end());
	cout << min;
	return 0;
}

너무 코드가 더럽다

이게 최선인가 싶다.

1. 비교할 체스판 2개 생성

2. 기준점을 바꿔가면서 목표 체스판과 비교 후 count push

3. 최솟값 출력

www.acmicpc.net/problem/11758

수업시간에 세 점이 이루는 꺾인선의 방향을 구해 교차여부를 알아내는 방법을 배웠다.

기억을 위해 거의 비슷한 문제로 복습을 해보았다.

#include<iostream>

using namespace std;

struct point {
	int x;
	int y;
}first, second;

struct line {
	struct point p1;
	struct point p2;
}testLine;

int direction(struct point A, struct point B, struct point C) {
	int dxAB, dxAC, dyAB, dyAC, Dir;
	dxAB = B.x - A.x; dxAC = C.x - A.x;
	dyAB = B.y - A.y; dyAC = C.y - A.y;

	if (dxAB * dyAC < dyAB * dxAC) Dir = -1;
	if (dxAB * dyAC > dyAB * dxAC) Dir = 1;
	if (dxAB * dyAC == dyAB * dxAC) {
		/*if (dxAB == 0 && dyAB == 0) Dir = 0;
		if ((dxAB * dxAC < 0) || (dyAB * dyAC < 0)) Dir = 1;
		else if ((dxAB * dxAB + dyAB * dyAB) >= (dxAC * dxAC + dyAC * dyAC)) Dir = 0;
		else Dir = -1;*/
		Dir = 0;
	}
	return Dir;
}

int main(void) {
	struct point A;
	struct point B;
	struct point C;

	int i,x, y;

	
	cin >> x >> y;
	A.x = x;
	A.y = y;
	cin >> x >> y;
	B.x = x;
	B.y = y;
	cin >> x >> y;
	C.x = x;
	C.y = y;
	

	cout <<direction(A, B, C);
	
	return 0;
}

이 문제는 세 점이 한 직선위에 존재한다는 가정을 뺀 상태이므로 세 점의 중간점이 무엇인지에 대한 부분은 주석처리 

했다.

www.acmicpc.net/step/34

고등 확률과 통계에서 배우는 순열과 조합이다.

순열과 조합을 구현하는데에 있어 매번 구글링 하기 귀찮아 좋은 정보를 얻어 정리를 해보려고한다.

출처 : hongchan.tistory.com/5

덕분에 좋은 정보를 얻었다.

순열 nPr

void printArray(int a[], int r) {
    for (int i = 0;i < r;i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void permutation(int pArr[], bool check[], int n, int r, int depth) {
    if (depth == r) {
        printArray(pArr, r);
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!check[i]) {
            check[i] = true;
            pArr[depth] = i;
            permutation(pArr, check, n, r, depth + 1);
            check[i] = false;
        }
    }
}

int main(void) {

    int n, r;
    cin >> n >> r;
    int* pArr = new int[r];
    bool* check = new bool[n + 1];
    for (int i = 0;i < r;i++) {
        pArr[i] = 0;
    }
    for (int i = 0;i < n + 1;i++) {
        check[i] = false;
    }
    permutation(pArr, check, n, r, 0);

    return 0;
}

1. pArr[] : n 까지의 숫자의 경우를 저장할 배열
2. check[] : 순열에서 중복의 여부를 확인하는 배열 ( 이 배열을 뺀다면 중복 순열이 된다. )

알고리즘 설명

1. check 가 false 인지 확인 ( 이미 나온 숫자인가? )
2. false 이면 true 로 할당
3. pArr[] 에 i 할당 ( 1부터 저장하기 위해 i = 1 로 지정 )
4. Permutation(...,depth + 1) 실행하여 중복되지 않는 수를 확인하고 배열에 삽입
5. depth == r 이 된다면 pArr 에 있는 원소 모두 출력
6. check 를 차례대로 false 로 할당하면서 함수 빠져나옴
7. for 문 반복

조합 nCr

void combination(int pArr[], int n, int r, int depth, int next) {
    if (depth == r) {
        printArray(pArr, r);
        return;
    }

    for (int i = next; i <= n; i++) {
        pArr[depth] = i;
        combination(pArr,n, r, depth + 1, i+1);// i+1 을 i로 바꿔주면 중복 허용
    }
}

int main(void) {

    int n, r;
    cin >> n >> r;
    int* pArr = new int[r];
    for (int i = 0;i < r;i++) {
        pArr[i] = 0;
    }
    combination(pArr, n, r, 0, 1);

    return 0;
}

순열과 다른 점 

• 조합은 순열과 달리 오름차순으로 정렬이 된다.

따라서, for 문의 i 값이 combination 이 실행될 수록 이 전 i 값보다 커야한다.

그리고, check[] 배열을 사용하지 않는 이유는 i 값을 늘려줌으로써 이전의 i 값이나 동일한 값이 들어가지 않기 때문이다.

그래서, i 의 값을 유지시킨다면 중복 조합이 된다. 

재귀로된 순열과 조합을 설명해 보았다.

하지만, 재귀인만큼 큰 수로 접근하게 된다면 overflow 발생 가능성도 있고 무엇보다 느리다.

이와 관련된 문제를 풀었었는데 까먹었다. ㅎㅎ