잡다한 프로그래밍

링크

https://swexpertacademy.com/main/main.do

1. 해결방법

1. 첫번째 생각으로 bfs를 이용하여 각 위치를 들리며 최소 시간을 구하는 방법을 사용하였다

하지만 bfs방법은 시간이 너무 오래걸려 문제의 시간을 초과해버려서 다른방법을 생각해보아야했다.

2. bfs를 사용하는 방법이지만 queue를 사용하였고 또한 cin, cout 대신 scanf와 printf를 사용하였다 cin과 cout보다 scanf와 printf가 속도가 더 빠르다고 하여 사용하여 시간을 단축하였다.

2. 코드

1. bfs방법(실패)

#include <iostream>
using namespace std;
int total = 0;
int num = 0;
int ary[100][100] = {};
int temp = 9999;
bool bo[100][100] = { false };
int sum = 0;
int nx[4] = { 0, 0, -1, 1 };
int ny[4] = { -1, 1, 0, 0 };

void dfs(int x, int y, int val) {
	bo[x][y] = true;

	if (x == num - 1 && y == num - 1) {
		if (temp > val) {
			temp = val;
			bo[x][y] = false;
			return;
		}
	}
	else {
		for (int i = 0; i < 4; i++) {
			int dx = x + nx[i];
			int dy = y + ny[i];

			if (dx < 0 || dx >= num || dy < 0 || dy >= num || bo[dx][dy] == true) continue;
			dfs(dx, dy, val + ary[dx][dy]);
			bo[dx][dy] = false;
		}
	}

}

int main()
{
	scanf("%1d", &total);
	for (int i = 0; i < total; i++) {

		scanf("%1d", &num);
		for (int j = 0; j < num; j++) {
			for (int k = 0; k < num; k++) {
				scanf("%1d", &ary[j][k]);
			}
		}


		temp = 9999;
		fill(&bo[0][0], &bo[0][0] + sizeof(bo), false);

		dfs(0, 0, ary[0][0]);

		cout << "#" << i + 1 << " " << temp << endl;

	}
}

2. queue를 이용한 bfs방법

#include <stdio.h>
#include <queue>
#include <memory.h>


using namespace std;
int total , num;
int ary[100][100];
int temp[100][100];
bool bo[100][100];
struct Node {
	int x;
	int y;
    Node(int _x, int _y) {
        x = _x;
        y = _y;
    }
};
void bfs() {
	queue<Node> q;
	q.push(Node(0, 0));
	bo[0][0] = true;
int dx[] = { 1,-1,0,0 };
    int dy[] = { 0,0,1,-1 };
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			 int ax = x + dx[i];
            int ay = y + dy[i];
			if (ax < 0 || ay < 0 || ax >= num || ay >= num ) continue;
                if (!bo[ax][ay] || temp[ax][ay] > temp[x][y] + ary[ax][ay]) {
               temp[ax][ay] = temp[x][y] + ary[ax][ay];
                    q.push(Node(ax, ay));
                    bo[ax][ay] = true;   
             }
		}
	}

}
void init() {
	memset(temp, 0, sizeof(temp));
	memset(bo, false, sizeof(bo));
}
int main()
{
    scanf("%d", &total);
    for (int i = 1; i <= total; i++) {
		init();
    scanf("%d", &num);
        char buf[101];
        for (int j = 0; j < num; j++) {
            scanf("%s", &buf);
			for (int k = 0; k < num; k++) {
			ary[j][k] = buf[k] - '0';
            }
		}
		bfs();
        printf("#%d %d\n", i, temp[num - 1][num - 1]);
	}
}

링크
https://swexpertacademy.com/main/main.do

1. 해결방법

모든 지점을 상 하 좌 우로 들리면서 7번째로 도착하면 set에 저장하면 자동으로 중복을 제거해 줄 수 있을 거라고 생각했다. 따라서 모든 지점을 상 하 좌 우로 들리는 방법을 코드로 구현하려 하였으나 결국 검색하여 찾아보니 dfs와 bfs방법을 사용한다고 한다. 이 문제의 해결방법으로는 dfs를 사용했고 dfs와 bfs는 따로 나중에 알고리즘에 추가하도록 할 예정이다.

2. 코드

#include <string>
#include <math.h>
#include <iostream>
#include <set>
using namespace std;

int num = 0;
int arr[4][4];
set<int> setary;
void dfs(int x, int y, int val, int dept) {
	int nx[4] = { 0, 0, -1, 1 };
	int ny[4] = { -1, 1, 0, 0 };
	for (int i = 0; i < 4; i++) {
		if (dept == 7) {
			setary.insert(val);
			return;
		}
		int dx = x + nx[i];
		int dy = y + ny[i];

		if (dx < 0 || dx >= 4 || dy < 0 || dy >= 4) continue;
		else {
			dfs(dx, dy, val * 10 + arr[dy][dx], dept + 1);
		}
	}
}
int main()
{
	cin >> num;
	for (int i = 1; i <= num; i++) {
        setary.clear();
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> arr[j][k];
			}
		}
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				dfs(j, k ,arr[j][k], 1);
			}
		}
		cout << "#"<< i << " " << setary.size() << endl;
	}
}

main함수에서 dfs(j, k, arr[j][k], 1)이 부분을 처음에 0, 0 arr[j][k], 1로 하였다 이때 값이 항상 같은 오류가 생겼고 이를 j k로 수정하며 해결하였다.

링크

1) 해결방법

배열로 입력값을 입력받은 후 양옆 두 칸 총 4칸 중 현재 칸보다 값이 크면 PASS, 값이 작다면 두 개의 차이 값을 구하여 가장 작은 차이 값이 View가 되는 값이라고 생각하였고 이를 코드로 구현하였다.

2) 코드

#include "pch.h"
#include <iostream>
#include <algorithm>

int main()
{
//10번 입력값을 받음
	for (int j = 0; j < 10; j++) {
		int input = 0;
		int result = 0;
		std::cin >> input;
		int array[1000] = { 0 };

		for (int i = 0; i < input; i++) {
			std::cin >> array[i];
		}
//3번째부터 마지막2칸을 제외한 97번째 까지 진행
		for (int i = 2; i < input - 2; i++) {
			int min = 9999;
			int minary[4] = { 0 };
            //현재값보다 양옆의 값이 더 크다면 continue
			if (array[i] <= array[i - 2] || array[i] <= array[i - 1] || array[i] <= array[i + 1] || array[i] <= array[i + 2]) {
				continue;
			}
			else {
				minary[0] = array[i] - array[i - 2];
				minary[1] = array[i] - array[i - 1];
				minary[2] = array[i] - array[i + 1];
				minary[3] = array[i] - array[i + 2];
				for (int i = 0; i < 4; i++) {
					min = std::min(min, minary[i]); //최소값 구함
				}
				result = result + min;
			}
		}
		std::cout << "#" << j + 1 << " " << result << std::endl;
	}

	return 0;
}