백준 3190번 뱀|AlgorithmBOJ|Algorithm

#3190. 뱀

문제링크

Problem

  • N x N 보드판
  • 양 끝 모서리에 벽이 있음
  • 뱀의 길이 1, 시작 위치 (1, 1), 방향: →
  • 매 초마다 이동
  1. 머리를 다음 칸에 위치
  2. 이동한 칸에 사과가 있으면 사과 먹고 꼬리 움직이지 않음(몸길이 늘어남)
  3. 꼬리 움직인다. (몸길이 그대로)

Goal: 사과의 위치와 뱀의 이동경로가 주어질 때 게임이 몇 초만에 끝나는지 계산

게임은 벽이나 자기자신의 몸과 부딪히면 끝난다.

뱀의 이동 경로는 (왼쪽 오른쪽 으로 90도 방향 회전)

  • 입력

방향 변환 정보에서 주어진 초는 게임 시작 시간으로부터 X초가 끝난 뒤를 말한다.

Solution

  • 주어진 문제대로 구현하면 된다. (시뮬레이션)
  • 방향전환 시간은 오름차순으로 주어지기에 queue에 저장
  • 사과가 있는 곳은 -1로 표시
  • 뱀이 있는 곳은 1부터~현재 길이까지 표시 (머리가 가장 큰 수)
  1. 머리를 기준으로 현재 방향에 맞게 움직인다.

  2. 머리가 움직였을 때 그곳이 벽이거나 자신의 몸인지 확인한다.
    필자는 다음과 같은 경우에 뱀이 동시에 움직일거라 생각하여 게임이 안끝난다고 생각했다.

    // 4가 머리이고 머리가 위쪽으로 가는 경우일 때
    1 2 -> 4 1
    4 3 3 2

하지만 동시에 움직이지 않고 머리부터 움직여서 꼬리가 따라온다. 그렇기에 위와 같은 경우는 게임이 종료된다.

  1. 방향 전환 시간인지 확인한다.
    해당 경우에 맞게 방향을 변경한다.

  2. 사과가 있는지 확인한다.
    사과가 있으면 길이가 1 늘어나고 이동하지 않는다.

  3. 이동한다.
    이동방법: 머리에서부터 시작해서 자신보다 1 적은 수를 찾는다. 찾으면 그 값을 넣는다. 이를 총 길이-1만큼 반복하고(머리를 제외하기 때문) 다음 탐색 부분에 머리를, 원래 꼬리 부분을 0으로 변경해준다.

    1 2 3 4 —> 1 1 2 3 —> 0 1 2 3

    5                4             5 4

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>  
#include <queue>
using namespace std;
int n, k, l;
int board[101][101];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int d_left[4] = { 2, 3, 1, 0 }; // 'L'
int d_right[4] = { 3, 2, 0, 1 }; // 'D'
queue<pair<int, char> > direction;
bool isWall(int x, int y) { // 벽이면 true
	if (x < 1 || y < 1 || x > n || y > n) return true;
	return false;
}
bool isBound(int x, int y) {
	if (x > 0 && y > 0 && x <= n && y <= n) return true;
	return false;
}
int game() {
	int x = 1; int y = 1; // 시작위치
	int dir = 3; // 시작방향: 오른쪽
	int len = 1; // 뱀의 길이
	int time = 0; // 게임 시작 시간
	board[x][y] = 1;
	while (true) {
		int convert = 0;
		if (!direction.empty()) {
			convert = direction.front().first;
		}
		time++;
		// 현재 방향에 맞는 한 칸 이동
		int d_x = x + dx[dir];
		int d_y = y + dy[dir];
		// 벽인지 자신의 몸인지 확인
		if (isWall(d_x, d_y) || board[d_x][d_y] > 0) return time;
		// 방향 전환 시간인지 확인
		if (time == convert) {
			if (direction.front().second == 'D') {
				dir = d_right[dir];
			}
			else {
				dir = d_left[dir];
			}
			direction.pop();
		}
		// 사과 있는지 확인
		if (board[d_x][d_y] == -1) {
			board[d_x][d_y] = ++len;
			x = d_x; y = d_y;
			continue;
		}
		// 이동
		int tmp_x = x, tmp_y = y;
		for (int i = 1; i < len; ++i) {
			for (int j = 0; j < 4; ++j) {
				int d_tmp_x = tmp_x + dx[j];
				int d_tmp_y = tmp_y + dy[j];
				if (isBound(d_tmp_x, d_tmp_y)) {
					if (board[d_tmp_x][d_tmp_y] == board[tmp_x][tmp_y] - 1) {
						board[tmp_x][tmp_y] = board[d_tmp_x][d_tmp_y];
						tmp_x = d_tmp_x; tmp_y = d_tmp_y;
						break;
					}
				}
			}
		}
		board[d_x][d_y] = len;
		board[tmp_x][tmp_y] = 0;
		x = d_x;
		y = d_y;
	}
}
int main() {
	scanf("%d %d", &n, &k);
	for (int i = 0; i < k; ++i) {
		int r, c;
		scanf("%d %d", &r, &c);
		board[r][c] = -1;
	}
	scanf("%d", &l);
	for (int i = 0; i < l; ++i) {
		int x; char dir;
		scanf("%d %c", &x, &dir);
		direction.push({ x, dir });
	}
	printf("%d\n", game());
	return 0;
}
백준 3055번 탈출|AlgorithmBOJ|Algorithm

#3055. 탈출

Problem

Solution

  • 조건 중에 “물이 찰 예정인 칸에 고슴도치가 움직일 수 없다.“에 집중하였다.
  • 물이 이동할 queue와 고슴도치가 이동할 queue를 따로 두어 탐색을 시작한다.
  • 단, 물이 먼저 이동해야 한다.(위 조건 때문에)
  • 모든 탐색은 BFS로 이루어지며, 물은 이동할 때마다 map을 갱신한다. 고슴도치는 갱신 안한다.
  • 고슴도치가 ‘D’에 도착하지 못 하고 탐색할 지점이 없을 때 -1을 리턴하여 도착할 수 없다는 것을 표시한다.
  • ‘D’에 도착하면 그때 시간을 바로 출력하도록 한다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <tuple>
#include <queue>
using namespace std;
int R, C;
char map[51][51];
bool visit[50][50];
queue<pair<int, int>> q;
queue<pair<int, int>> water;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
void Input() {
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < C; ++j) {
			scanf(" %c", &map[i][j]);
			if (map[i][j] == 'S') { q.push({ i, j }); visit[i][j] = true; }
			else if (map[i][j] == '*') water.push({ i, j });
		}
	}
}
bool isBound(int x, int y) {
	if (x > -1 && y > -1 && x < R && y < C) return true;
	return false;
}
int BFS() {
	int time = 0;
	while (!q.empty()) { // 고슴도치가 탐색할 지점이 없을 때까지 진행
		int w_len = water.size();
		for (int i = 0; i < w_len; ++i) { // 물의 이동
			int water_x, water_y;
			tie(water_x, water_y) = water.front();
			water.pop();  
			for (int dir = 0; dir < 4; ++dir) {
				int d_w_x = water_x + dx[dir];
				int d_w_y = water_y + dy[dir];
				if (isBound(d_w_x, d_w_y)) {
					if (map[d_w_x][d_w_y] == '.' || map[d_w_x][d_w_y] == 'S') {
						map[d_w_x][d_w_y] = '*';
						water.push({ d_w_x, d_w_y });
					}
				}
			}
		}
		int len = q.size();
		for (int i = 0; i < len; ++i) { // 고슴도치 이동
			int x, y;
			tie(x, y) = q.front();
			q.pop();
			if (map[x][y] == 'D') return time; // 목적지 도착하면 시간 리턴
			for (int dir = 0; dir < 4; ++dir) {
				int d_x = x + dx[dir];
				int d_y = y + dy[dir];
				if (isBound(d_x, d_y) && !visit[d_x][d_y]) {
					if (map[d_x][d_y] != 'X' && map[d_x][d_y] != '*') {
						visit[d_x][d_y] = true;
						q.push({ d_x, d_y });
					}
				}
			}
		}
		time++;
	}
	return -1;
}
void Solve() {
	int ans = BFS();
	if (ans == -1) printf("KAKTUS\n");
	else printf("%d\n", ans);
}
int main() {
	Input();
	Solve();
	return 0;
}
백준 2869번 달팽이는 올라가고 싶다|AlgorithmBOJ|Algorithm

#2869. 달팽이는 올라가고 싶다

Problem

높이 V미터인 나무막대

  • 낮에 A미터 올라감
  • 밤에 B미터 내려감
  • 정상에서는 안내려감

나무 막대 모두 올라가는데 걸리는 일 수

하루에 +A -B

B < A ≤ V ≤ 10억

어차피 값은 10억을 넘을 수 없으니 int 사용해도 무방

Ex.

 input
2 1 5
 output
4
  • 설명

1일: 0+2 = 2

2일: 2-1+2 =3

3일: 3-1+2 = 4

4일: 4-1+2 = 5

하지만 제한시간이 0.15초이기에 이런 단계로 풀면 안된다.
하루는 무조건 A가 되고 그 후는 -B+A가 반복이니 다음이 성립한다.

하지만 x는 정수이므로 위와 같은 부등호를 붙여주어야 한다.

3 1 6

1일: 3

2일: 3-1+3 = 5

3일: 5-1+3 = 7

공식: x ≥ 1.xx 따라서 x는 2, 총 일 수는 2+1 = 3일이된다.

  • 근데 이 공식 적용하면 V가 되었다가 다시 줄어드는 경우가 있어서 답에 영향을 주나? → NO
  • ceil() 때문에 피연산자는 double형으로, 결과값은 int형으로 두었다.
    (결과값을 double로 설정하면 출력값이 큰 경우 부동소수점 방식으로 출력되어 틀린 답이 된다.)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include <iostream>
    #include <cmath>
    using namespace std;
    int main() {
        double a, b, v;
        int day = 1;
        cin >> a >> b >> v;
        double ans = (v-a) / (a-b);
        ans = ceil(ans);
        day += ans;
        cout << day << endl;
        return 0;
    }
백준 2798번 블랙잭|AlgorithmBOJ|Algorithm

#2798. 블랙잭

  • N장의 카드
  • M : 목표
  • N장의 카드 중 3개 선택
  • 3개의 숫자 합이 M에 최대한 가깝도록(M을 넘어서면 안됨)

N은 최대 100이기에 100장 중 3장을 선택하는 경우의 수 100 x 99 x 98 = 970,200‬가 최대이다.
그러므로 충분히 모든 경우의 수를 구해 답을 찾아낼 수 있는 문제이다.

재귀나 for문을 이용하여 풀 수 있을 것이다.

필자는 재귀를 사용하였다.

M은 최대 300000이기에 MAX 값으로 두었고 재귀의 내용은 다음과 같다.

  • 매개변수
    • numbers : N개의 숫자를 담을 vector
    • goal : M
    • ans : 숫자 합
    • index : numbers의 인덱스
    • selected : 남은 카드 선택 횟수
  • 실패 조건
    • 숫자 합이 M보다 클 때
    • index가 numbers의 크기를 넘었을 때
  • 성공 조건
    • 3번을 뽑았을 경우, goal과 ans의 차이가 최소인 값
  • 재귀함수
    • 카드를 선택하지 않을 때
    • 카드를 선택했을 때
      ans에 선택한 카드가 더해짐
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      #include <iostream>
      #include <vector>
      #define MAX 300000;
      using namespace std;
      int min_diff = MAX;
      vector<int> numbers;
      void doCombination(vector<int> numbers, int goal, int ans, int index, int selected) {
          if(ans > goal) return;
          if(selected == 0) {
              min_diff = min_diff > goal-ans ? goal-ans : min_diff;
              return;
          }
          if(index >= numbers.size()) {
              return;
          }
          doCombination(numbers, goal, ans, index+1, selected); // not selected
          ans += numbers[index];
          doCombination(numbers, goal, ans, index+1, selected-1); // selected
      }
      int main() {
         int n, m, answer = 0;
         cin >> n >> m;
         numbers.resize(n);
         for(int i = 0; i < n; ++i) {
             cin >> numbers[i];
         }
         doCombination(numbers, m, 0, 0, 3);
         answer = m - min_diff;
         cout << answer << endl;
         return 0;
      }
백준 2748번 피보나치 수 2|AlgorithmBOJ|Algorithm

#2748. 피보나치 수 2

문제링크

Problem

  • Goal : n번째 피보나치 수를 구하여라
  • condition
    • 최대 90번째 피보나치 수를 구할 수 있어야 함
    • 시간 제한 1초

Solution

수식 그대로 DP를 적용한다.

1
2
// dp[n]은 n번째 피보나치 수
dp[n] = dp[n-1] + dp[n-2];

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
long long dp[91]; 
long long fibo(int n)
{
	dp[0] = 0, dp[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}

int main()
{
	int n;
	cin >> n;
	cout << fibo(n) << endl;
	return 0;
}

주의할 점은 90번째 피보나치 수(10의 18승보다 큼)를 담으려면 long long을 써야 한다는 점이다.(long은 안된다.)

백준 2468번 안전 영역|AlgorithmBOJ|Algorithm

#2468. 안전 영역

Problem

Solution

  1. 높이 1부터 최대 높이까지 작업을 진행한다. → set에 높이 정보를 담고 오름차순으로 정렬하면 더 빠를듯
  2. 각 높이마다 모든 영역을 탐색한다. (말이 모든 영역이지 이미 높이보다 같거나 작은 영역이나 방문한 영역이면 탐색을 하지 않는다.)
    탐색은 BFS로 안전영역을 표시한다.
  3. 탐색이 끝나면 안전 영역의 수를 1증가한다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int N, max_height, ans = 1;
int arr[100][100];
bool visited[100][100];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
void BFS(int x, int y, int h) {
	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[x][y] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
			if (visited[nx][ny] || arr[nx][ny] <= h) continue;
			visited[nx][ny] = true;
			q.push({ nx, ny });
		}
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> arr[i][j];
			if (max_height < arr[i][j]) max_height = arr[i][j];
		}
	}
	for (int h = 1; h <= max_height; ++h) {
		int area = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j] || arr[i][j] <= h) continue;
				BFS(i, j, h);
				area++;
			}
		}
		if (ans < area) ans = area;
		memset(visited, false, sizeof(visited));
	}
	cout << ans << "\n";
	return 0;
}
백준 2251번 물통|AlgorithmBOJ|Algorithm

#2251. 물통

Problem

Solution

  • 첫 시작은 C 물통만 가득 차 있으니 전체 합은 C의 물통이다.
  • 물을 옮기는 경우는 총 6경우로 0을 A, 1을 B, 2를 C라고 했을 때 다음과 같은 경우가 존재한다.
    1
    2
    3
    0 -> 1, 0 -> 2
    1 -> 0, 1 -> 2
    2 -> 0, 2 -> 1
  • 경우의 수가 중복되지 않도록 표시해주는 배열은 2차원으로도 해결 가능하다. (전체 양은 일정하니 A, B만 알아도 C를 알 수 있기 때문이다.)
  1. 처음 A, B, C의 부피를 저장한다.
  2. 시작은 (0, 0)에서 시작하고, ans[C 물의 양]이 true임을 표시해 A가 0일 때 C의 물의양임을 나타낸다.
  3. BFS 탐색을 시작한다. 각 경우에서 계속해서 나아가는 방식이기에 적합하다. (경우의 수도 많지 않음)

  4. 물을 옮기는 건 2가지 경우가 존재한다.

    from x → to y

    1. x + y ≤ Y
      x + y의 값이 y를 가진 물통의 부피(Y)이하일 때
      x를 다 옮길 수 있으므로 x를 가졌던 물통의 물의 양은 0이 된다.
      y를 가진 물통의 물의 양은 x+y가 된다.
    2. x + y > Y
      x + y의 값이 Y보다 클 때 x를 다 옮길 수 없으므로
      x를 가졌던 물통의 물의 양은 x + y - Y가된다.
      y를 가졌던 물통의 물의 양은 Y가 된다.
    1. check와 A의 물의 양이 0인지 판단하여 BFS 탐색을 한다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <queue>
using namespace std;
int bucket[3]; // 물통 부피
bool check[201][201]; // A, B만 알아도 C를 알 수 있음
bool ans[201]; // A가 비어있을 때 C의 물의 양
queue<pair<int, int>> q;
int from[6] = { 0, 0, 1, 1, 2, 2 }; // 0: A, 1: B, 2: C
int to[6] = { 1, 2, 0, 2, 0, 1 };
void Output() {
	for (int i = 0; i <= 200; ++i) {
		if (ans[i]) cout << i << " ";
	}
	cout << "\n";
}
void BFS() {
	int sum = bucket[2];
	q.push({ 0, 0 });
	check[0][0]= true;
	ans[sum] = true;
	while (!q.empty()) {
		int cur[3];
		cur[0] = q.front().first;
		cur[1] = q.front().second;
		cur[2] = sum - cur[0] - cur[1];
		q.pop(); 
		for (int i = 0; i < 6; ++i) {
			int next[3] = { cur[0], cur[1], cur[2] };
			if (next[from[i]] + next[to[i]] <= bucket[to[i]]) { 
				next[to[i]] += next[from[i]];
				next[from[i]] = 0;
			}
			else { // 옮긴 물의 양이 해당 물통 부피보다 클 때
				next[from[i]] += next[to[i]] - bucket[to[i]];
				next[to[i]] = bucket[to[i]];
			}
			if (!check[next[0]][next[1]]) {
				check[next[0]][next[1]] = true;
				q.push({ next[0], next[1] });
				if (next[0] == 0) ans[next[2]] = true;
			}
		}
	}	
}
int main() {
	for (int i = 0; i < 3; ++i) cin >> bucket[i];
	BFS();
	Output();
	return 0;
}
백준 2231번 분해합|AlgorithmBOJ|Algorithm

#2231. 분해합

문제링크

Problem

  • 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합
  • 245의 분해합 : 245+2+4+5 = 256
    245는 256의 생성자
  • 생성자는 없을 수도 여러 개일 수도 있음
    • 없다면 0 출력

Goal: N이 주어졌을 때 N의 가장 작은 생성자 출력

Solution

  • 1부터 최대 N-1까지 분해합을 구하면서 풀어보면 어떻게 될까?
  • 1부터 분해합을 구하다가 N이 되었을 때 종료하면 가장 작은 생성자를 출력할 수 있다.
  • 분해합 구하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    212의 분해합 구하기
    212  자릿수 3
    // #1.
    212 / 10^2 = 2 -> 212+2
    212 - 2*10^2 = 12
    // #2.
    12 / 10^1 = 1 -> 212+2+1
    12 - 1*10^1 = 2 -> 212+2+1+2

    11의 분해합 구하기
    11 자릿수 2
    div = 10 (10의 제곱 수)
    sum = 11 (분해합)
    // #1.
    temp = 11 / 10 = 1 (계산 용도)
    num = 11 - 10 = 1
    sum = 11 + 1 = 12
    div = 1
    // #2.
    temp = 1 / 1 = 1
    num = 1 - 1 = 0
    sum = 12 + 1 = 13
    div = 0

    그냥 더 간단한 방법이 생각났다. (2 Try 참고)
    sum, temp = 11
    sum = 11 + 11 % 10
    temp = 11 / 10 = 1
    sum = 12 + 1 % 10 = 13
    즉, 
    sum += temp % 10
    temp /= 10

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cmath>
using namespace std;
// 자릿 수 체크
int getLength(int num) {
	int count = 0;
	do {
		count++;
	}while(num/=10);
	return count;
}
// 분해합 게산 
int distributeSum(int num) {
	int length = getLength(num);
	int div = pow(10, length-1);
	int sum = num; int temp;
	for(int i = 0; i < length; ++i) {
		temp = num / div; 
		num = num - temp * div; 
		sum += temp; 
		div /= 10;
	}
	return sum;
}
int main()
{
	int n, i;
	cin >> n;
	for(i = 1; i < n; ++i) {
		if(n == distributeSum(i)) {
			cout << i << '\n';
			break;
		}
	}
	if(i == n) cout << 0 << '\n';
	return 0;
}

108ms

2 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int distributeSum(int num) {
	int sum, temp;
	sum = temp = num;
	do {
		sum += temp % 10;
	}while(temp /= 10);
	return sum;
}
int main() {
	int n, i;
	cin >> n;
	for(i = 1; i < n; ++i) {
		if(n == distributeSum(i)) {
			cout << i << '\n';
			break;
		}
	}
	if(i == n) cout << 0 << '\n';	
	return 0;
}

8ms

백준 2206번 벽 부수고 이동하기|AlgorithmBOJ|Algorithm

#2206. 벽 부수고 이동하기

문제링크

Problem

  • N x M 크기의 맵
  • 0은 이동가능 1은 벽을 나타냄
  • (0, 0) → (N-1, M-1)까지 이동 (상하좌우)
  • 벽을 1개까지 부수고 이동 가능

Goal: (0, 0)에서 (N-1, M-1)까지 이동하는데 걸리는 경로 중 최단 경로 구하기

Solution

  • 이동하기

시작지점(0, 0)에서부터 상하좌우로 갈 수 있는 방향을 탐색한다.
도착지점까지 모든 곳을 탐색해야 하며, 이때 BFS를 사용한다.
현재 지점에서 상하좌우로 가는데 걸리는 비용이 동일하기 때문이다.

  • 벽을 부수었는지 여부를 경로를 갱신할 때마다 가지고 있어야 한다.

탐색할 때 이미 값이 있다면 이미 지나온 경로이므로 다른 지점을 탐색해야 한다. 그외는 다음을 확인하고 경로를 갱신한다.

  1. 탐색할 지점이 0이라면 경로 갱신
  2. 탐색할 지점이 1인데 이전까지 벽을 부수지 않았다면 경로 갱신

위와 같은 작업으로 문제를 해결할 수 있다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <queue>
#define MAX 1001
using namespace std;
int n, m;
int map[MAX][MAX];
int path[MAX][MAX][2]; // 벽을 안부순 경로, 벽을 부순 경로
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
struct INFO {
	int r, c;
	bool break_wall = false;
};
int bfs() {
	queue<INFO> q;
	q.push({ 0, 0, false });
	path[0][0][0] = 1;
	while (!q.empty()) {
		int r = q.front().r; int c = q.front().c;
		bool bw = q.front().break_wall;
		q.pop();
		if (r == n - 1 && c == m - 1) return path[r][c][bw];
		for (int i = 0; i < 4; ++i) {
			int x = r + dx[i];
			int y = c + dy[i];
			if (x > -1 && y > -1 && x < n && y < m) {
				if (path[x][y][bw]) continue;
				if (map[x][y] == 0) {
					path[x][y][bw] = path[r][c][bw] + 1;
					q.push({ x, y, bw });
				}
				else if(map[x][y] == 1 && bw == 0) {
					path[x][y][1] = path[r][c][bw] + 1;
					q.push({ x, y, true });
				}
			}
		}
	}
	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", &map[i][j]);
		}
	}
	printf("%d\n", bfs());
	return 0;
}
백준 2146번 다리 만들기|AlgorithmBOJ|Algorithm

2146. 다리 만들기

Problem

Solution

  1. 각 섬의 id를 매긴다. → DFS 이용

  2. 가장 짧은 다리의 길이를 구한다. → BFS 이용

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int map[100][100];
bool visited[100][100];
int N, ans =1e9;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
void DFS(int x, int y, int idx) {
	visited[x][y] = true;
	map[x][y] = idx;
	for (int dir = 0; dir < 4; ++dir) {
		int d_x = x + dx[dir];
		int d_y = y + dy[dir];
		if (d_x > -1 && d_y > -1 && d_x < N && d_y < N) {
			if (map[d_x][d_y] == 0 || visited[d_x][d_y]) continue;
			DFS(d_x, d_y, idx);
		}
	}
}
int BFS(int x, int y) {
	memset(visited, false, sizeof(visited));
	queue<pair<int, int>> q;
	q.push({ x, y });
	int temp = map[x][y];
	int res = 0;
	while (int len = q.size()) {
		while(len--) {
			int x = q.front().first;
			int y = q.front().second;			
			q.pop();
			for (int dir = 0; dir < 4; ++dir) {
				int d_x = x + dx[dir];
				int d_y = y + dy[dir];
				if (d_x > -1 && d_y > -1 && d_x < N && d_y < N) {
					if (map[d_x][d_y] != 0 && map[d_x][d_y] != temp) return res;
					if (map[d_x][d_y] == 0 && !visited[d_x][d_y]) {
						visited[d_x][d_y] = true;
						q.push({ d_x, d_y });
					}
				}
			} 
		}
		res++;
	}
	return ans;
}
int main() {
	cin >> N; int idx = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> map[i][j];
		}
	}
	// 각 섬에 번호 매기기
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (visited[i][j] || map[i][j] == 0) continue;
			DFS(i, j, idx++);
		}
	}
	// 가장 짧은 다리 길이 구하기
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (map[i][j] == 0) continue;
			ans = min(ans, BFS(i, j));
		}
	}
	cout << ans << "\n";
	return 0;
}