씅의 기록하는 개발노트

문제 출처

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

문제풀이

아마 처음 긴장을 풀어주기 위해 1번 문제로 준비한 문제가 아닐까 싶다. 이 문제에서의 핵심은 스택을 사용하는 거라 생각한다. 바구니는 아래칸부터 인형이 순서대로 쌓이는 구조이며 이는 한쪽에서만 입력이 일어남을 알 수 있다. 크레인이 인형을 뽑고나서 스택의 top과 뽑은 인형이 같다면 스택을 pop하고 정답을 2 더해주면 되는 문제이다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%ED%81%AC%EB%A0%88%EC%9D%B8%20%EC%9D%B8%ED%98%95%EB%BD%91%EA%B8%B0%20%EA%B2%8C%EC%9E%84.cpp

#include <string>
#include <vector>
#include <stack>
using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    stack<int> s;
    for (int i=0; i<moves.size(); i++) {
        int x = moves[i] - 1;
        
        for (int y=0; y<board.size(); y++) {
            if (board[y][x] == 0) continue;

            if (!s.empty() && (s.top() == board[y][x])) {
                s.pop();
                answer += 2;
            } else {
                s.push(board[y][x]);
            }
            
            board[y][x] = 0;
            break;
        }
    }
    return answer;
}

문제출처

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

문제풀이

최단거리를 구하는 문제이므로 BFS를 사용했다. 이 문제에서 가장 중요한 거는 input이 붙어서 주어진다는 것이다. 나 같은 경우는 map에 미로 정보를 입력하고 bfs탐색시작점을 1로 시작해 탐색한 거리마다 기존 값+1을 해주는 방식으로 풀이했다.

미로의 출구는 항상 map[n-1][m-1]의 위치이기 때문에 모든 탐색을 다 한뒤 거리를 저장한 배열의 n행 m열의 값을 출력해주면 된다. 

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_2178/boj2178.cpp

#include <cstdio>
#include <queue>
using namespace std;
int n, m;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
int map[100][100];
int dist[100][100];
void bfs(int y, int x) {
	queue<pair<int, int> > q;
	q.push(make_pair(y, x));
	dist[y][x] = 1;

	while (!q.empty()) {
		y = q.front().first;
		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 >= m || dist[ny][nx] != 0 || map[ny][nx] != 1) continue;

			q.push(make_pair(ny, nx));
			dist[ny][nx] = dist[y][x] + 1;
		}
	}
}
int main() {
	scanf("%d %d", &n, &m);
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			scanf("%1d", &map[y][x]);
		}
	}
	bfs(0, 0);
	printf("%d\n", dist[n - 1][m - 1]);
	return 0;
}

문제출처

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

문제풀이

DFS, BFS 2가지 그래프 탐색 알고리즘 어떤 것을 써도 풀이 가능한 문제다. 나는 BFS를 사용했는데 입력을 받는 map배열과 방문여부를 확인하는 visit배열을 사용해서 풀이했다.

단지번호붙이기 문제와 같은 유형인데 단지 4방향 -> 8방향으로 확대되었다는 것밖에 바뀐게 없다.

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_4963/boj4963.cpp

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int w, h;
const int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int map[50][50];
bool visit[50][50];
void bfs(int y, int x) {
	queue<pair<int, int> > q;
	q.push(make_pair(y, x));
	visit[y][x] = 1;

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

		for (int i = 0; i < 8; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= h || nx >= w || visit[ny][nx]) continue;
			if (map[ny][nx] == 1) {
				q.push(make_pair(ny, nx));
				visit[ny][nx] = 1;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	while (1) {
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		memset(map, 0, sizeof(map));
		memset(visit, 0, sizeof(visit));
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				cin >> map[y][x];
			}
		}

		int landCount = 0;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				if (map[y][x] == 1 && visit[y][x] == 0) {
					bfs(y, x);
					landCount++;
				}
			}
		}
		cout << landCount << "\n";
	}
	return 0;
}