3-D 메모리 초과 질문드립니다
338
작성한 질문수 6
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
http://boj.kr/78f586fab057402f93621ce7d148e6bb
지도를 입력받을 때 탈출 부분을 벡터에 push_back 하고
사람과 불을 각각 bfs 돌렸습니다.
탈출 부분 벡터를 반복문으로 돌면서
탈출이 가능한 경우 그 시간을 ret 벡터에 넣고
ret의 크기가 0이면 impossible을 출력하고
0이 아니면 정렬하여 맨 앞의 숫자를 출력하도록 했는데
메모리 초과가 뜹니다... ㅠㅠ 왜그럴까요?
답변 1
0
안녕하세요 qn님 ㅎㅎ
이부분에서 문제가 있는 거 같습니다.
디버깅코드를 넣어봤는데요.
while (q.size()) {
tie(y, x) = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < r && ny >= 0 && nx < c && nx >= 0 && m[ny][nx] != '#') {
if (visited[ny][nx] > visited[y][x]) {
cout << visited[ny][nx] << '\n';
visited[ny][nx] = visited[y][x] + 1;
q.push({ ny, nx });
}
}
}
cout << q.size() << "\n";
}이렇게 디버깅 해보시겠어요?
이부분에서 무한루프가 걸리며 q.size()가 계속해서 증가하는 모습이 보입니다.
반례
10 100
....................................................................................................
.......###############.......FFFF..........########.................................................
.........FFFFFFFFFFFFF#############...........................FFF..........##########....########...
.....................................................................######..................####...
.......FF...................................J.......................................................
.............................................................................................####...
......................###############################################...............................
....................................................................................................
.........FFFFFFFFFFFFF............####..........................................FFFFFF....FFFFF.....
.............................................###.######.............................................
답 : 7
해당 부분에 반례를 해결하려면
이런식으로 바꿔야 하지 않을까요? 방문을 안했다면 >> 방문처리
if (visited[ny][nx] == 2e9) {
그리고 이 반례 부분을 해결 못하고 있습니다.
5 5
FFFFF
..J..
.....
.....
.....
답 : 4
이 부분은
for (auto a : fire) {
bfs(a.first, a.second);
}이런식으로 fire마다 순차적으로 bfs를 돌려서 그런데요. fire부분을 q에 담아서 bfs를 한꺼번에 돌려야 하지 않을까요?
감사합니다.
0
http://boj.kr/972b9dbcb4b24d56a34b37744dde4aec
원래 fire마다 순차적으로 bfs를 돌리는 것이 목표였습니다. 순차적으로 bfs를 진행하면서
이전의 불들이 현재 위치까지 걸리는 시간(visited에 계속 기록)보다
현재 돌리는 fire가 현재 위치에 도달하는 시간이 더 적을 경우
그 적은 시간을 갱신하는 식으로 visited를 완성해나가고자 했습니다.
그 후 지훈이가 이동하는 거리를 visited2에 기록한 후 벡터에 넣어놨던 탈출 위치를
반복문을 통해 돌면서 지훈 이동 거리(visited2)가 불 거리(visited)보다 작을 경우
지훈이가 해당 탈출 위치에 더 빨리 도착한다는 것이므로 그 거리들을 벡터에 넣어놓고
정렬하여 가장 작은 거리를 마지막에 출력하고자 했습니다.
이전 시도했던 코드는 bfs 함수에서 if (visited[ny][nx] > visited[y][x]) 이 부분 때문에
계속 큐 사이즈가 올라 갔습니다. 어쩌피 ny, nx는 현재 위치에서 상하좌우 한 칸씩 이동한 곳이기 때문에 그 차이가 한 칸이라면 탐색할 이유가 없어서(같은 거리이므로) if (visited[ny][nx] > visited[y][x] + 1)로 조건을 고쳤습니다.(위 링크)
근데 이렇게 수정하니 메모리 초과는 안뜨지만 여전히 에러가 나옵니다.
어떤 반례가 있는 걸까요....?
0
안녕하세요 ㅎㅎ
원래 fire마다 순차적으로 bfs를 돌리는 것이 목표였습니다. 순차적으로 bfs를 진행하면서
이전의 불들이 현재 위치까지 걸리는 시간(visited에 계속 기록)보다
현재 돌리는 fire가 현재 위치에 도달하는 시간이 더 적을 경우
그 적은 시간을 갱신하는 식으로 visited를 완성해나가고자 했습니다.
>> 해당 로직은 이해했는데요. ㅎㅎ 근데 사실 그러한 로직은 비효율적입니다.
if (ny < r && ny >= 0 && nx < c && nx >= 0 && m[ny][nx] != '#') {
if (visited[ny][nx] > visited[y][x] + 1) {bfs는 방문한 정점은 다시 방문하지 않는다. 라는 특징을 가지고 해당 부분 때문에 빠릅니다. 근데 이 코드는 방문한 정점을 다시 방문하게 되죠.
즉, 비효율적이게 됩니다.
이를 queue에다가 시작 F정점들을 담아두고 단한번만 bfs를 돌리게 수정하는게 좋습니다.
어떤 반례가 있는 걸까요....?
>> 반례는 몇개 시도해봤는데 잘 안나오네요...
찾는대로 답변 드리겠습니다.
감사합니다.
0
반례 찾았습니다. ㅎㅎ
예를 들어
FF..
이렇게 되어있을 때
오른쪽 F부터 bfs가 시작되면
2123
이렇게 visited배열이 완성되겠죠?
근데 여기서
왼쪽 F이 시작되면
1234
이렇게 되어버리지 않을까요?
원래는 이게 맞을 거 같습니다.
1123
감사합니다.
0
항상 빠른 답변 감사합니다!
2123 상태에서 왼쪽 F가 시작되면 bfs를 호출해서 우선 1123이 될테고(while문 이전 초기화)
while문에 들어가면 if (visited[ny][nx] > visited[y][x] + 1) 조건을 만족시키지 못하기 때문에
더이상 큐에 push가 되지 않고 1123이 그대로 유지될 것 같은데요...?
실제로 돌려보면 0012로 출력됩니다.(전 시작할 때 0으로 지정해서 1씩 빠진 값으로 출력됩니다)
0
더이상 큐에 push가 되지 않고 1123이 그대로 유지될 것 같은데요...?
>> 네 그러네요..ㅜㅜ...이게 최솟값으로 갱신되서 그러는거 같습니다.
하하 하지만 반례를 찾았습니다.
3 3
.FF
..J
...
답 : 1
수강생님 코드 : 2
감사합니다.
0
else if를 잘못 설정해서 지훈이가 탈출 지역에 있을 때
탈출점을 push_back할 때 누락되는 부분이 있었군요
해당 부분을 아래와 같이 고쳤습니다.
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> m[i][j];
if (m[i][j] == 'J') pos = { i,j };
else if (m[i][j] == 'F') fire.push_back({ i, j });
if (i == r - 1 || j == c - 1 || i == 0 || j == 0) {
if (m[i][j] != '#') {
esc.push_back({ i,j });
}
}
}
}
드디어! 를 외치며 제출을 했는데 어림도 없었습니다....
이전과 같이 계속 2%에서 틀렸습니다 가 나오네요 ㅠㅠ
사실 강의보고 해당 알고리즘 대로 코드 구성해서 이미 해결한 문제이긴 한데
처음 생각했던 알고리즘도 말이 된다 싶어서 계속 시도해보고 있어요...
계속 반례가 나오는데 그만 놓아주어야 할까요...?
0
넴.. 놓아주어야 할 것 같습니다.
사실 저도 여러번 시도를 하고 있는데요.
이상하게 안되네요..
제가 qn님 코드 수정한 부분은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
int r, c, cnt;
char m[1004][1004];
int visited[1004][1004];
int visited2[1004][1004];
vector<pair<int, int>> fire;
vector<pair<int, int>> esc;
vector<int> ret;
void bfs2(int y, int x) {
visited2[y][x] = 0;
queue<pair<int, int>> q;
q.push({ y, x });
while (q.size()) {
tie(y, x) = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < r && ny >= 0 && nx < c && nx >= 0 && m[ny][nx] != '#' && visited2[ny][nx] == -1) {
visited2[ny][nx] = visited2[y][x] + 1;
q.push({ ny, nx });
}
}
}
}
void bfs() {
int y, x;
queue<pair<int, int>> q;
for (auto a : fire) {
tie(y, x) = a;
visited[y][x] = 0;
q.push({ y, x });
}
while (q.size()) {
tie(y, x) = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < r && ny >= 0 && nx < c && nx >= 0 && m[ny][nx] != '#' && visited[ny][nx] == 2e9) {
visited[ny][nx] = visited[y][x] + 1;
q.push({ ny, nx });
}
}
//cout << q.size() << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
fill(&visited[0][0], &visited[0][0] + 1004 * 1004, 2e9);
fill(&visited2[0][0], &visited2[0][0] + 1004 * 1004, -1);
cin >> r >> c;
pair<int, int> pos;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> m[i][j];
if (m[i][j] == 'J') pos = { i,j };
else if (m[i][j] == 'F') fire.push_back({ i, j });
else if (i == r - 1 || j == c - 1 || i == 0 || j == 0) {
if (m[i][j] != '#') {
esc.push_back({ i,j });
}
}
}
}
bfs();
bfs2(pos.first, pos.second);
for (auto a : esc) {
if (visited2[a.first][a.second] < visited[a.first][a.second]) {
ret.push_back(visited2[a.first][a.second] + 1);
}
}
if (ret.size() == 0) {
cout << "IMPOSSIBLE";
}
else {
sort(ret.begin(), ret.end());
cout << ret.front();
}
//cout << '\n';
//for (int i = 0; i < r; i++) {
// for (int j = 0; j < c; j++) {
// cout << visited[i][j] << ' ';
// }
// cout << '\n';
//}
//for (int i = 0; i < r; i++) {
// for (int j = 0; j < c; j++) {
// cout << visited2[i][j] << ' ';
// }
// cout << '\n';
//}
return 0;
}0
해결했습니다.
3 3
..F
.J#
.#.
이런 경우에서 [2][2]에 해당하는 자리가
visited2에서 -1(기본값 fill)로 초기화 된 후 방문 되지 않기 때문에
if (visited2[a.first][a.second] < visited[a.first][a.second]) (visited2 = 지훈, visited = 불)
이 조건문에 무조건 성립되어 ret 벡터에 -1에서 1을 더한 0 값이 들어가서
ret 벡터를 sort 후 답(벡터의 front())을 출력하면 0이 출력되는 문제가 있었습니다.
많은 답변 정말 감사합니다!!!
4 - A
0
21
2
코딩살구클럽 입장이 안됩니다
0
55
2
4-F 경우의 수 질문입니다.
0
32
2
코딩살구클럽 가입이 안됩니다.
0
66
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
54
1
교안 158페이지 문의드립니다
0
44
2
코딩살구클럽 관련 건의사항
0
110
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
44
1
진행 방법 질문드립니다!
0
79
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
63
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
313
2
백준 서비스 종료
9
945
1
sk 하이닉스 코테 대비
0
384
2
3-G 최댓값 질문
0
54
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
63
2
3-N 질문 있습니다.
0
68
2
학습방법
0
105
2
4-H 질문 있습니다 (코드 리뷰)
0
69
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
182
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
71
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
65
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
53
2