글 읽기 - 주석 달아놨으니 도와주시면 감사하겠습니다. c++

oh_hyerin 3년 전 0

안녕하세요!

저는 제 로직이 맞는 거 같은데 어디가 틀렸는지 잘 모르겠습니다,,,,,

봐주시면 감사하겠습니다!

#include<iostream>
#include<string>
#include<vector>
#include<algorithm> 
#include<queue>
using namespace std;

vector<vector<char>> map;
vector<vector<int>>visited;
queue<pair<int,int>>que;

int n , m;
int dx[] = { -1,1,0,0 } ;
int dy[] = { 0,0,-1,1 };

int bfs(int i, int j) {
	visited.resize(n, vector<int>(m, 0));	//visited 모두 0으로 초기화
	que.push({ i,j }); // 시작값을 큐에 넣어줌
	visited[i][j] = 1; // visited[시작값] = 1
	int n_max = 1;
	while (!que.empty()) {
		int x = que.front().first;
		int y = que.front().second;
		que.pop();
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x;
			int ny = dy[i] + y;
			//범위를 벗어나지 않는 내에서 육지이면서 visited가 0 즉, 아직 안지난곳이라면 큐에 집어넣음
			if (nx > -1 && nx < n && ny > -1 && ny < m && map[nx][ny] == 'L' && visited[nx][ny]== 0) {
				visited[nx][ny] = visited[x][y] + 1; // 그 다음 좌표는 이전 좌표에서 한 시간 추가해줘야함 
				que.push({ nx,ny });
				if (n_max < visited[nx][ny]) n_max = visited[nx][ny];
			}
		}
	}
	return n_max;
}

int main() {
	cin >> n >> m;
	//입력받기
	map.resize(n, vector<char>(m, 0));
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < m; j++) {
			map[i][j] = str[j];
		}
	}
	int max_path = 1;

	//육지인곳에서만 bfs 실시 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 'L') {
				int path = bfs(i, j);
				max_path = max(path, max_path);
			}
		}
	}
	//visited[초깃값] = 1 이므로 1 뺴줌
	cout << max_path - 1;
}

doju 3년 전 0

resize(n, T)는 현재 벡터의 크기가 n보다 작을 때 늘어나는 공간을 T로 채워 주는 역할을 합니다. 따라서 17번째 줄은 bfs가 처음 호출될 때 단 한 번만 초기화를 하고, 그 뒤로는 아무 일도 하지 않습니다.

oh_hyerin 3년 전 0

헠 정말 감사합니다!

고치니까 바로 맞았습니다가 뜨네요 ㅎㅎ

resize가 초기화의 기능이 되는 줄 알았는데 아니었네요 ㅜㅜ 공부를 더해야할 거 같습니다.

정말 감사합니다!

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

문제

문제

출처

ICPC

주석 달아놨으니 도와주시면 감사하겠습니다. c++

oh_hyerin 3년 전 0

doju 3년 전 0

oh_hyerin 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말