씅의 기록하는 개발노트

문제출처

https://programmers.co.kr/learn/courses/30/lessons/59045

문제풀이

보호소에 들어올 당시에는 중성화되지 않았지만, 보호소를 나갈때 중성화된 동물'을 찾는 문제이다.

키 값으로 INNER JOIN을 한뒤 ANIMAL_INS에서는 Intact로 시작하고, ANIMAL_OUTS에서는 Spayed나 Neutered로 시작하는 데이터를 찾으면 된다.

소스코드

SELECT A.ANIMAL_ID
      ,A.ANIMAL_TYPE
      ,A.NAME
FROM   ANIMAL_INS A
      ,ANIMAL_OUTS B
WHERE  A.ANIMAL_ID   = B.ANIMAL_ID
AND    A.ANIMAL_TYPE = B.ANIMAL_TYPE
AND    A.SEX_UPON_INTAKE LIKE 'Intact%'
AND    (B.SEX_UPON_OUTCOME LIKE 'Neutered%' OR B.SEX_UPON_OUTCOME LIKE 'Spayed%')

문제출처

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

문제풀이

BFS로 전체탐색하면 되는 문제이다. 

BFS탐색을 통해 연합국가들을 찾으며 총 인구수와 연합국가 수를 구한다. 연합국가가 있는 경우 값을 문제조건대로 갱신해주고 연합국가가 없는경우 인구이동이 일어난 회수를 출력해주면 된다.

이때 연합국가의 좌표를 vector에 저장해 따로 관리해 주면서 갱신해줬다. 삼성기출문제가 점점 응용력이 필요해지는 것 같다. 문제를 주의깊게 읽고 완벽히 이해한뒤 소스코드를 작성하도록 해야겠다.

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_16234/BOJ_16234/boj16234.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
bool flag;
int n, l, r, ans;
int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };
int map[50][50];
bool visit[50][50];
vector<pair<int, int> > v;
void init() {
	cin >> n >> l >> r;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
		}
	}
}
void bfs(int y, int x) {
	int count = 1, sum = map[y][x];
	queue<pair<int, int> > q;
	q.push(make_pair(y, x));
	v.push_back(make_pair(y, x));
	visit[y][x] = 1;
	
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= n || nx >= n || visit[ny][nx]) continue;

			int diff = abs(map[y][x] - map[ny][nx]);
			if (diff >= l && diff <= r) {
				visit[ny][nx] = 1;
				sum += map[ny][nx];
				count++;
				q.push(make_pair(ny, nx));
				v.push_back(make_pair(ny, nx));
			}
		}
	}

	if (v.size() > 1) {
		flag = 1;
		int updateValue = sum / count;
		for (int i = 0; i < v.size(); i++) map[v[i].first][v[i].second] = updateValue;	
	}
	v.clear();
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	while (true) {
		memset(visit, 0, sizeof(visit));
		flag = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				if (visit[y][x]) continue;
				bfs(y, x);
			}
		}
		if (flag) ans++;
		else break;
	}
	cout << ans << "\n";
	return 0;
}

문제출처

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

문제풀이

그냥 진짜 구현하는 문제다. 빡구현까지는 아니고 배열 조정을 하느라 약간 머리가 아픈 문제

문제에 나온대로 확산과 공기청정기 순환 2가지로 나눠서 구현하면 된다.

spreadDust() 메서드

확산은 tempMap배열을 이용해 구현했다. 확산은 queue를 이용해도 될것같다.

확산과 같은 경우 인접한 공간에 숫자가 있는경우 어떻게 처리하는지가 중요하다. 한 공간(y, x)를 기준으로 인접한 공간에 값이 없다면 그냥 4방향으로 확산시켜주면 되지만, 한 방향이라도 있는 경우 다음 탐색을 할때 영향을 주기 때문이다. 즉, 우리는 순차적으로 한 공간(y, x)에 대해 확산시키는 소스를 구현하지만 문제는 한순간에 확산하기 때문에 영향을 받기전의 값으로 확산을 시켜야 한다.

1. map을 tempMap에 복사하여 원래의 미세먼지 값들을 저장.

2. 확산될 먼지의 양은 원본map을 통해 계산

3. tempMap에서 먼지를 확산시킴

4. tempMap에서 확산시킨 것들 다시 map으로 옮김.

activateAirCleaner() 메서드

이 부분은 공기청정기를 작동시키는 메서드이다. 기존 입력을 받을때 따로 list에 저장해둔 공기청정기의 y좌표를 이용해 map배열의 값을 옮겨주면 된다. 공기청정기에 들어가는 먼지는 없어진다는 조건을 활용해서 없어지는 좌측부터 하나씩 값을 옮겨주었다. 여기서 주의할 점은 공기청정기가 위치한 y좌표의 x축을 이동시킬때 모두 이동시키고 공기청정기 다음x좌표를 0으로 다시 갱신해줘야 한다는 것이다.

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_17144/boj17144.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static int r, c, t;
    private static int dy[] = {0, -1, 0, 1};
    private static int dx[] = {1, 0, -1, 0};
    private static int map[][];
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;
    private static ArrayList<Integer> cleaner;

    public static void main(String[] args) throws Exception {
        init();
        while (true) {
            t--;
            spreadDust();
            activateAirCleaner();

            if (t == 0) {
                System.out.println(countDustVolumn());
                break;
            }
        }
    }

    private static int countDustVolumn() {
        int ret = 0;
        for (int y=0; y<r; y++) {
            for (int x=0; x<c; x++) {
                if (map[y][x] != 0 && map[y][x] != -1) ret += map[y][x];
            }
        }
        return ret;
    }

    private static void copyMap(int src[][], int dest[][]) {
        for (int y=0; y<r; y++) {
            for (int x=0; x<c; x++) {
                dest[y][x] = src[y][x];
            }
        }
    }

    private static void activateAirCleaner() {
        int upY = cleaner.get(0);
        int downY = cleaner.get(1);

        // 위쪽
        for (int y=upY-1; y>0; y--) {
            map[y][0] = map[y-1][0];
        }
        for (int x=0; x<c-1; x++) {
            map[0][x] = map[0][x+1];
        }
        for (int y=0; y<upY; y++) {
            map[y][c-1] = map[y+1][c-1];
        }
        for (int x=c-1; x>0; x--) {
            map[upY][x] = map[upY][x-1];
        }
        map[upY][1] = 0;

        // 아래쪽
        for (int y=downY+1; y<r-1; y++) {
            map[y][0] = map[y+1][0];
        }
        for (int x=0; x<c-1; x++) {
            map[r-1][x] = map[r-1][x+1];
        }
        for (int y=r-1; y>=downY; y--) {
            map[y][c-1] = map[y-1][c-1];
        }
        for (int x=c-1; x>1; x--) {
            map[downY][x] = map[downY][x-1];
        }
        map[downY][1] = 0;
    }

    private static void spreadDust() {
        int tempMap[][] = new int[r][c];
        copyMap(map, tempMap);

        for (int y=0; y<r; y++) {
            for (int x=0; x<c; x++) {
                if (map[y][x] != 0 && map[y][x] != -1) {
                    int count = 0;
                    int dust = map[y][x] / 5;
                    for (int i=0; i<4; i++) {
                        int ny = y+dy[i];
                        int nx = x+dx[i];

                        if (ny<0 || nx<0 || ny>=r || nx>=c || map[ny][nx] == -1) continue;
                        tempMap[ny][nx] += dust;
                        count++;
                    }
                    tempMap[y][x] -= (count * dust);
                }
            }
        }
        copyMap(tempMap, map);
    }

    private static void init() throws Exception {
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        map = new int[r][c];
        cleaner = new ArrayList<>();

        for (int y=0; y<r; y++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int x=0; x<c; x++) {
                map[y][x] = Integer.parseInt(st.nextToken());
                if (map[y][x] == -1) cleaner.add(y);
            }
        }
    }
}