글 읽기 - c++ 문제는 맞았는데 왜 맞았는지 모르겠습니다.

celestial 3년 전 0

간단히 말해서 dp로 풀어야한다고 생각했습니다. 그런데 일일이 시작점을 찾고,

그 시작점의 최단거리중 가장 긴 값을 계속 갱신을 하는 방식으로 이어나가면

시간 복잡도가 엄청나게 될 것 같아서 dp로 풀어야 할지 그냥 풀어도 괜찮을런지 고민이 많았습니다.

왜냐하면 일일이 풀면

50 * 50 사이즈에 L밖에 없다 가정하였을 때 2500

그 모든 시작점에 대해 2500*2500을 하면 6250000

효율이 안나올 것 같아서요ㅜㅜ!!

그런데 그냥 일일이 푸는 방식으로 풀면 왜 맞는지

그리고 dp로 풀면 어떻게 구할 수 있는지 아이디어 좀 조언해주시면 감사하겠습니다.

감사합니다!

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>

using namespace std;

char map[51][51];
bool visited[51][51];
int dp[51][51];


int n, m;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int maxi = -1;
int cnt = 0;
queue<pair<pair<int, int>,int>>Q;

void BFS() {

	pair<pair<int, int>,int> current;
	while (!Q.empty()) {
		//current = Q .front();
		current.first.first = Q.front().first.first;
		current.first.second = Q.front().first.second;
		current.second = Q.front().second;
		Q.pop();
		//printf("current movecnt : %d \n\n", current.second);
		for (int i = 0; i < 4; i++) {

			int x = current.first.first + dx[i];
			int y = current.first.second + dy[i];


			if (x < 1 || y < 1 || x > n || y > m) {
				continue;
			}
			if (map[x][y] == 'W') { continue; }
			if (visited[x][y]) { continue; }

			if (!visited[x][y] && map[x][y] == 'L') {
				visited[x][y] = true;
				pair<pair<int, int>, int>next;
				next.first.first = x;
				next.first.second = y;
				next.second = current.second+1;
				//("next : %d %d %d \n\n", next.first.first, next.first.second, next.second);
				Q.push(next);

			}



		}
	}
	if (current.second > maxi) {
		maxi = current.second;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			visited[i][j] = false;
		}
	}


}



int main() {

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> map[i][j];
		}
	}


	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!visited[i][j] && map[i][j] == 'L') {
				visited[i][j] = true;
				pair<pair<int, int>,int>start;
				start.first.first = i;
				start.first.second = j;
				start.second = 0;
				//printf("start : %d %d %d\n\n", start.first.first, start.first.second, start.second);
				Q.push(start);
				BFS();

			}



		}
	}
	printf("%d", maxi);





}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 문제는 맞았는데 왜 맞았는지 모르겠습니다.

celestial 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말