코딩하는 두꺼비

www.acmicpc.net/problem/16234

구현 문제이자 BFS로서 생각보다 크게 어렵진 않았지만 배열 크기 선언과 범위 설정하느라

계속 틀리다가 맞추었다. N*N으로 배열을 선언해야하는데 그 생각을 못하고 그냥 N으로 선언한 것이 패착이였다.

실제 시험장에서는 항상 변수 선언을 할때 생각을 하면서 해야할거 같다..

풀이는 BFS로 연합의 개수를 세고 각 2차원 배열로 각 연합의 인구수를 계산해서 저장을 해놓고

마지막에 인구수를 나눈 값을 넣어주는 형식으로 구성했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int N, L, R, ans, cnt = 1;
int map[51][51];
int visit[51][51];
int people[2555][2];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
queue<pair<int, int>> q;

void bfs(int x, int y) {
	q.push({ x, y });
	visit[x][y] = cnt;
	people[cnt][1]++;
	people[cnt][0] += map[x][y];

	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			int a = q.front().first;
			int b = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {		//국경을 열 수 있는지 확인
				int c = a + dx[j];
				int d = b + dy[j];
				if (c >= 0 && d >= 0 && c < N && d < N && visit[c][d] == 0 
					&& abs(map[a][b] - map[c][d]) >= L
					&& abs(map[a][b] - map[c][d]) <= R) {
					q.push({ c, d });
					visit[c][d] = cnt;
					people[cnt][0] += map[c][d];
					people[cnt][1]++;
				}
			}
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	while (1) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visit[i][j] == 0) {
					bfs(i, j);
					cnt++;	//연합 갯수 증가
				}
			}
		}
		for (int i = 0; i < N; i++) {	//연합 안의 사람들 재분배
			for (int j = 0; j < N; j++) {
				if (visit[i][j] > 0) {
					map[i][j] = people[visit[i][j]][0] / people[visit[i][j]][1];
				}
			}
		}
		if (cnt > N * N) {	//연합의 갯수가 N*N이면 중단
			break;
		}
		ans++;
		cnt = 1;
		memset(people, 0, sizeof(people));	//배열 초기화
		memset(visit, 0, sizeof(visit));
	}
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/2665

첨에 어떻게 접근할 지 고민하다가 방금 푼 문제였던 벽 부수고 이동하기의 코드를 활용해서 풀었다.

사실 최솟값이 필요없기 때문에 좀 비효율적으로 코드를 짠 것 같아서 좀 아쉽다..

다음에 풀 때는 그 전의 바꾼 방갯수를 비교해서 최신화하는 식을 짜봐야겠다..

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;

struct map {
    int x, y, w;
};

int n, ans = -1;
int a[51][51];
int dist[51][51][100];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };

int bfs(int b) {
    queue<map> q;
    q.push({ 0, 0, 0 });
    dist[0][0][0] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int w = q.front().w;
        q.pop();
        if (x == n - 1 && y == n - 1) {
            return dist[x][y][w];
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (dist[nx][ny][w]) continue;
            if (a[nx][ny] == 1) {
                dist[nx][ny][w] = dist[x][y][w] + 1;
                q.push({ nx, ny, w });
            }
            if (a[nx][ny] == 0 && w < b) {
                dist[nx][ny][w+1] = dist[x][y][w] + 1;
                q.push({ nx, ny, w+1 });
            }
        }
    }
    return -1;
}

int main() {
    int b = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    while (1) {
        ans = bfs(b);
        if (ans >= 0) {
            printf("%d", b);
            break;
        }
        else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k <= b; k++) {
                        dist[i][j][k] = 0;
                    }
                }
            }
        }
        b++;
    }
    return 0;
}

www.acmicpc.net/problem/2206

정말 고민을 많이 한 문제였는데.. 접근방식이 계속 틀린 것이 문제였다...

BFS에 다가 자신의 상태를 저장을 해주어야 하는데 그 생각을 못하고 시작점과 끝점에서 BFS를 두번돌려서 만나는 지점이 같으면 벽을 부수는 걸로 접근을 했었다.

답지를 보기 싫었는데 결국 보게 되서 좀 아쉬운 문제였고 아직 멀었구나 느꼈다..

참고 블로그: rebas.kr/658

이 블로그의 해답이 제일 깔끔하고 이해가 잘되었다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;

struct map {
    int x, y, w;
};

int n, m;
int a[1001][1001];
int dist[1001][1001][2];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };

int bfs() {
    queue<map> q;
    q.push({ 0, 0, 0 });
    dist[0][0][0] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int w = q.front().w;
        q.pop();
        if (x == n - 1 && y == m - 1) {
            return dist[x][y][w];
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (dist[nx][ny][w]) continue;
            if (a[nx][ny] == 0) {
                dist[nx][ny][w] = dist[x][y][w] + 1;
                q.push({ nx, ny, w });
            }
            if (a[nx][ny] == 1 && w == 0) {
                dist[nx][ny][1] = dist[x][y][w] + 1;
                q.push({ nx, ny, 1 });
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    printf("%d", bfs());
    return 0;
}