BOJ 17130

30 Jan 2020 • ProblemSolving

토끼가 정보섬에 올라온 이유

문제출처

1.설계(10)

  • 문제 해석

    • 토끼가 쪽문으로 탈출 할 때, 가장 많이 들고갈 수 있는 당근 수를 구하는 문제입니다.
    • 3 방향으로 이동이 가능하고, 쪽문을 통해 탈출이 가능하며 탈출하지 않아도 됩니다.

  • 설계

    • 3방향으로 이동할 때, 이전의 당근을 가지고 있는 개수의 정보가 이용되므로 dp를 사용해도 될것 같습니다.
    • 또한, deque을 이용해서 당근이 위치해 있는 곳을 우선적으로 탐색 하는 방법으로 구현이 가능할 것 같습니다.
    • 저는 dp를 사용하지 않고 두번째 방법을 이용하였습니다.

2.구현(35)

  • 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <deque>
using namespace std;
#define MAXN 1000

struct node {
	int x;
	int y;
	int cnt;
};
int N, M;
deque<node> dq;
int dx[] = { 0,1,-1 };
int dy[] = { 1,1,1 };
char map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int bfs() {
	int ans = -1;
	while (!dq.empty()) {
		int x = dq.front().x;
		int y = dq.front().y;
		int cnt = dq.front().cnt;
		
		if (map[x][y] == 'O') {
			if (ans < cnt) ans = cnt;
		}
		dq.pop_front();
		for (int k = 0; k < 3; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			if (map[nx][ny] == '#') continue;
			if (visited[nx][ny]) continue;
			visited[nx][ny] = true;
			if (map[nx][ny] != 'C') {
				dq.push_back({ nx,ny,cnt });			
			}
			else {
				dq.push_front({ nx,ny,cnt+1 });
			}
		}
	}
	return ans;
}
int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf(" %1c", &map[i][j]);
			if (map[i][j] == 'R') {
				dq.push_back({ i,j});
				visited[i][j] = true;
			}
		}
	}
	cout << bfs() <<"\n";
	return 0;
}

  • 디버깅

    • 처음에 queue와 dist를 이용하여 dist[nx][ny] < dist[x][y]+1 일 경우(당근이 없는 곳은 dist[nx][ny] < dist[x][y] 조건을 사용)만 탐색하도록 구현했는데 WA가 나왔습니다.
    • 그래서 queue를 deque으로 대체하였습니다.

  • 제출결과

    68ms

3.마무리

  • 대부분 dp를 이용하여 구현한 것을 공개코드를 통해 확인하였습니다.
    한가지의 고정된 알고리즘으로 사용하지 않고 다양한 방법을 시도해 보기위해서 bfs+deque 을 이용하여 구현하였습니다.
 BOJ

Related Posts