굳건하게

문제 : https://www.acmicpc.net/problem/1806

[ 알고리즘풀이 ]

 Two-Pointer를 이용해 배열을 한 번 순회하면서 S보다 크거나 같은 가장 작은 구간을 찾을 수 있다.

1. list 배열을 Pointer( j ), Pointer( i ) 를 이용해 앞에서부터 순회하며 구간의 합을 구한다.

  ( 이때, j 는 시작점 i 는 끝점을 의미한다. )

2. 끝점인 i 를 올려가며 배열을 순회하다 Sum이 S보다 크거나 같아지는 순간( 즉,  j ~ i 까지의 합이 S보다 크거나 같아졌다 ), j ~ i 까지의 합이 여전히 S보다 큰 시점까지 시작점인 j 도 올린다. 그러면 현재 상태에서의 최소 길이가 만들어지므로 답을 갱신하면 된다.

#include<iostream>
#include<algorithm>
#define INF 987654321

using namespace std;

int N, S, list[100000] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> S;
	for (int i = 0; i < N; i++)
		cin >> list[i];

	int i = 0, j = 0, sum = 0, minLength = INF;
	while (i < N) {
		sum += list[i];
		if (sum >= S) {
			while (sum - list[j] >= S) {
				sum -= list[j++];
			}
			minLength = min(minLength, i - j + 1);
		}
		i++;
	}
	if (minLength == INF)
		minLength = 0;
	cout << minLength;
	return 0;
}

문제 : https://www.acmicpc.net/problem/2589

[ 알고리즘풀이 ]

 Input으로 주어지는 Map이 크지 않으므로, 모든 육지에서 BFS 탐색을 진행해 해당 육지에서 가장 먼 육지까지의 거리를 구하고 답을 갱신해주면 된다.

#include<iostream>
#include<queue>

using namespace std;

int N, M, ans = -1, dx[4] = { -1,0,1,0 }, dy[4] = { 0, 1, 0, -1 };
char map[51][51];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 'L') {
				bool check[51][51] = {};
				queue<int> x, y, l;
				x.push(i), y.push(j), l.push(0);
				check[i][j] = true;
				while (!x.empty()) {
					int curX = x.front(), curY = y.front(), curL = l.front();
					x.pop(), y.pop(), l.pop();
					ans = max(ans, curL);
					for (int k = 0; k < 4; k++) {
						int nextX = curX + dx[k];
						int nextY = curY + dy[k];
						if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M) {
							if(map[nextX][nextY] == 'L' && check[nextX][nextY] == false){
								x.push(nextX), y.push(nextY), l.push(curL + 1);
								check[nextX][nextY] = true;
							}
						}
					}
				}
			}
		}
	}
	cout << ans;
	return 0;
}

문제 : https://www.acmicpc.net/problem/16236

[ 알고리즘풀이 ]

1. 현재 상어 위치에서 BFS 탐색을 진행해 갈 수 있는 모든 곳을 탐색하며 먹을 수 있는 물고기의 거리, 좌표를 담는다.

2.

- 먹을 수 있는 물고기가 없다면 종료

- 있다면 가장 가까우면서 상단에 있으면서 왼쪽에 있는 즉 거리가 작고, x 좌표가 작고, y 좌표가 작은 순으로 sort 한 후 가장 앞에 있는 물고기를 먹으면 된다.

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

using namespace std;

int N, map[20][20], sX, sY, sS = 2, sC = 0, time = 0;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };

void Init(void) {
	while(1){
		if (sS == sC){
			sC = 0, sS++;
		}
		// 지금 상어가 먹을 수 있는 물고기의 거리와 좌표를 담자.
		vector<pair<int, pair<int, int>>> fish;

		// BFS 탐색을 하자.
		bool checkMap[20][20] = {};
		queue<pair<pair<int, int>, int >> q;
		checkMap[sX][sY] = true;
		q.push(make_pair(make_pair(sX, sY), 0));
		while (!q.empty()) {
			pair<pair<int, int>, int> temp = q.front();
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nextX = temp.first.first + dx[i], nextY = temp.first.second + dy[i];
				if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) { // map을 벗어나지않고
					if (checkMap[nextX][nextY] == false && map[nextX][nextY] <= sS) { // 처음가보는데 지나갈 수 있는곳
						checkMap[nextX][nextY] = true;
						q.push(make_pair(make_pair(nextX, nextY), temp.second + 1));
						if (map[nextX][nextY] != 0 && map[nextX][nextY] < sS) { // 먹을 수 있는 물고기
							fish.push_back(make_pair(temp.second + 1, make_pair(nextX, nextY)));
						}
					}
				}
			}
		}
		if (fish.empty())
			break;
		// 가까운 거리가 왼쪽 상단부터 sort된다.
		sort(fish.begin(), fish.end());
		// 첫 번째 물고기를 먹으면 된다.
		time += fish[0].first;
		sX = fish[0].second.first, sY = fish[0].second.second, sC++;
		map[sX][sY] = 0;
	}	
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for(int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				sX = i, sY = j;
				map[sX][sY] = 0;
			}
		}
	Init();
	cout << time;
	return 0;
}

문제 : https://www.acmicpc.net/problem/13460

( 저번 포스팅 : https://travelbeeee.tistory.com/322 )

( 참고한 포스팅 : https://jason9319.tistory.com/217 )

[ 알고리즘 ]

 내가 구현한 알고리즘이 다른 알고리즘에 비해 수행 시간 면에서 너무 느리고 단순히 생각해봐도 꼭 백트레킹을 이용해 10번 회전하는 모든 경우의 수에 대해서 찾은 다음에 회전할 필요도 없이, 회전을 진행해나가며 답을 찾으면 Stop 하는 것이 효율적임을 알 수 있었다. 따라서, 문제를 다시 풀어보았다.

 하지만, BFS탐색을 이용해서 경우의 수를 늘려가더라도, 현재 'R', 'B' 위치에 따라서 Map의 모양이 바뀌는데 이 문제를 어떻게 해결해야 하나 답을 찾지 못했다,,,,

 그래서 다른 고수분들의 코드를 공부하던 중, '자손9319' 님의 코드가 너무 아름다워서 분석을 해보려고 한다,,,!

아래는 '자손9319' 님의 코드다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, disc[11][11][11][11], bx, by, rx, ry;
char a[11][11];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int bfs() {
    queue<pair<pair<int, int>, pair<int,int>>> qu;
    qu.push({ {rx,ry},{bx,by} });
    disc[rx][ry][bx][by] = 1;
    int ret = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            int x = qu.front().first.first;
            int y = qu.front().first.second;
            int z = qu.front().second.first;
            int w = qu.front().second.second;
            qu.pop();
            if (a[x][y] == 'O'&&a[x][y] != a[z][w])
                return ret;
            for (int i = 0; i < 4; i++) {
                int cx = x, cy = y, cz = z, cw = w;
                while (a[cx + dx[i]][cy + dy[i]] != '#'&&a[cx][cy] != 'O') {
                    cx += dx[i];
                    cy += dy[i];
                }
                while (a[cz + dx[i]][cw + dy[i]] != '#'&&a[cz][cw] != 'O') {
                    cz += dx[i];
                    cw += dy[i];
                }
                if (cx == cz&&cy == cw) {
                    if (a[cx][cy] == 'O')continue;
                    if (abs(cx - x) + abs(cy - y) < abs(cz - z) + abs(cw - w)) {
                        cz -= dx[i];
                        cw -= dy[i];
                    }
                    else {
                        cx -= dx[i];
                        cy -= dy[i];
                    }
                }
                if (disc[cx][cy][cz][cw])continue;
                qu.push({ {cx,cy} ,{cz,cw} });
                disc[cx][cy][cz][cw] = 1;
            }
        }
        if (ret == 10)
            return -1;
        ret++;
    }
    return -1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            scanf("%c", &a[i][j]);
            if (a[i][j] == 'B') {
                bx = i;
                by = j;
            }
            else if (a[i][j] == 'R') {
                rx = i;
                ry = j;
            }
        }
    }
    printf("%d\n", bfs());
    return 0;
}


출처: https://jason9319.tistory.com/217 [ACM-ICPC 상 탈 사람]

1. disc 4차원 배열.

disc 4차원 배열을 통해 BFS 탐색을 진행하면서 이미 과거에 'R', 'B' 가 현재 위치에 있었던 경우는 탐색을 중단한다.

2. dx, dy 배열

dx, dy 배열을 통해서 4개의 방향에 대해서 깔끔하게 이동할 수 있다. 이때, '#', 'O'가 아닌 경우에는 계속 이동을 진행한다.

3. 빨간 구슬과 파란 구슬이 겹치는 경우 해결.

 예를 들어 오른쪽으로 기울여야 되는데 빨간 구슬과 파란 구슬이 같은 행에 있고, 빨간 구슬이 파란 구슬보다 더 왼쪽에 있다고 하자. 그렇다면, 더 오른쪽에 있는 파란 구슬을 먼저 이동해야 하므로 파란 구슬을 이동시키고, 빨간 구슬을 이동시켜야 한다고 생각했고, 그러다 보니 기존의 내 코드는 복잡해졌다.

 하지만, '자손9319' 님은 일단 이동시킨 후에,  둘이 겹친다면( 즉 기울이는 과정에서 하나가 먼저 이동하고 다른 하나가 이동해야 하는 경우 ) 아래의 코드를 통해서 깔끔하게 문제를 해결하는 것을 볼 수 있다.

                    if (abs(cx - x) + abs(cy - y) < abs(cz - z) + abs(cw - w)) {
                        cz -= dx[i];
                        cw -= dy[i];
                    }
                    else {
                        cx -= dx[i];
                        cy -= dy[i];
                    }

 내가 걱정하던 현재 진행되는 경우에서 'R', 'B' 의 위치에 따라 map이 조금씩 다른데 이 부분을 어떻게 해결할까는 사실 이 문제에서 고려를 하지 않아도 되는 부분이었다. 그냥 'R', 'B' 위치가 있으면 모든 방향에 대해서 기울이고 우리는 '#', 'O' 인지 아닌지만 신경 쓰면 됐다....! 내가 지금 이동시킨 곳이 'R' 인지 'B' 인지는 신경 쓰지 않아도 이동시키고 빨간 구슬과 파란 구슬이 겹친다면 위의 코드를 이용해 위치를 적절히 갱신해주면 되는 일이었다.

알고리즘 잘하고 싶다,,,