인프런 커뮤니티 질문&답변
작성한 질문수
3-D 메모리초과 질문있습니다
작성
·
95
0
#include <bits/stdc++.h>
using namespace std;
int R, C, fire_visitied[1000][1000]={0,}, jihoon_visitied[1000][1000]={0,};
int dy[4]={-1,0,1,0}, dx[4]={0,1,0,-1};
char arr[1000][1000]={0,};
pair<int,int> jihoon, fire;
vector<pair<int,int>> fire_v;
void fire_bfs(int y, int x){
queue<pair<int,int>> que;
fire_visitied[y][x]=1;
que.push({y,x});
while(que.size()){
pair<int,int> temp=que.front();
que.pop();
for (int i=0;i<4;i++){
int ny=temp.first+dy[i];
int nx=temp.second+dx[i];
if (ny<0||nx<0||ny>=R||nx>=C) continue;
if (arr[ny][nx]=='#'||(fire_visitied[ny][nx]&&(fire_visitied[ny][nx]<fire_visitied[temp.first][temp.second]+1))) continue;
fire_visitied[ny][nx]=fire_visitied[temp.first][temp.second]+1;
que.push({ny,nx});
}
}
}
int jihoon_bfs(int y, int x){
queue<pair<int,int>> que;
jihoon_visitied[y][x]=1;
que.push({y,x});
while(que.size()){
pair<int,int> temp=que.front();
que.pop();
for (int i=0;i<4;i++){
int ny=temp.first+dy[i];
int nx=temp.second+dx[i];
if (ny<0||nx<0||ny>=R||nx>=C) return jihoon_visitied[temp.first][temp.second];
if (jihoon_visitied[ny][nx]||arr[ny][nx]=='#') continue;
if (jihoon_visitied[temp.first][temp.second]+1>=fire_visitied[ny][nx]) continue;
jihoon_visitied[ny][nx]=jihoon_visitied[temp.first][temp.second]+1;
que.push({ny,nx});
}
}
return 0;
}
int main()
{
cin >> R >> C;
for (int i=0;i<R;i++){
for (int j=0;j<C;j++){
cin >> arr[i][j];
if (arr[i][j]=='J') jihoon={i,j};
if (arr[i][j]=='F') fire_v.push_back({i,j});
}
}
if (!fire_v.size()) fill(&fire_visitied[0][0],&fire_visitied[0][0]+1000*1000,INT_MAX);
for (auto i:fire_v) fire_bfs(i.first,i.second);
int answer=jihoon_bfs(jihoon.first,jihoon.second);
if (answer) cout << answer;
else cout << "IMPOSSIBLE";
}위 코드에서 메모리 초과가 납니다. 초기의 모든 불의 위치를 큐에 담아서 bfs 를 하는 것을 생각하지 못해 모든 불을 돌면서 bfs를 하도록 코딩했습니다.
if (arr[ny][nx]=='#'||(fire_visitied[ny][nx]&&(fire_visitied[ny][nx]<fire_visitied[temp.first][temp.second]+1))) continue;이 라인을 통해서 fire 배열의 중복을 막은 것 같은데 왜 메모리초과가 나는지 모르겠습니다. 알려주시면 감사하겠습니다 ㅠ
답변 1
0
큰돌
지식공유자
안녕하세요 ㅎㅎ
사실 그부분만 빼면 괜찮은 코드입니다.
저도 처음에는 그 부분 살려가면서 고치려고 했는데 왜인지 모르게 메모리초과나 틀렸습니다가 뜨더군요.
그럴 때 저는 보통 코드 다듬기를 합니다.
일단.. 저부분은 일단은 비효율적이기 때문에 다듬고.. 다른 부분도 최대한 수강생님 코드 살려가면서 다듬어봤는데요.
#include <bits/stdc++.h>
using namespace std;
int R, C;
int fire_visited[1004][1004];
int jihoon_visited[1004][1004];
int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
char arr[1004][1004];
pair<int, int> jihoon;
vector<pair<int, int>> fire_v;
void bfs_fire() {
queue<pair<int, int>> q;
for (auto &f : fire_v) {
q.push(f);
fire_visited[f.first][f.second] = 1;
}
while (!q.empty()) {
auto [y, x] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny >= 0 && nx >= 0 && ny < R && nx < C && arr[ny][nx] != '#' && (!fire_visited[ny][nx] || fire_visited[ny][nx] > fire_visited[y][x] + 1)) {
fire_visited[ny][nx] = fire_visited[y][x] + 1;
q.push({ny, nx});
}
}
}
}
int bfs_jihoon() {
queue<pair<int, int>> q;
q.push(jihoon);
jihoon_visited[jihoon.first][jihoon.second] = 1;
while (!q.empty()) {
auto [y, x] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= R || nx >= C) return jihoon_visited[y][x];
if (!jihoon_visited[ny][nx] && arr[ny][nx] != '#' && (fire_visited[ny][nx] == 0 || jihoon_visited[y][x] + 1 < fire_visited[ny][nx])) {
jihoon_visited[ny][nx] = jihoon_visited[y][x] + 1;
q.push({ny, nx});
}
}
}
return 0;
}
int main() {
cin >> R >> C;
memset(fire_visited, 0, sizeof(fire_visited));
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> arr[i][j];
if (arr[i][j] == 'J') jihoon = {i, j};
else if (arr[i][j] == 'F') {
fire_v.push_back({i, j});
fire_visited[i][j] = 1;
}
}
}
bfs_fire();
int answer = bfs_jihoon();
if (answer) cout << answer;
else cout << "IMPOSSIBLE";
return 0;
}
이렇게 한번 해보시겠어요?
전체적인 로직은 정말 잘 짜셨습니다. ㅎㅎ
틀린부분을 명확하게 알려주고 싶은데 마음대로 되지 않네요.
그래도 최대한 다듬어 봤습니다. ㅎㅎ
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.