인프런 커뮤니티 질문&답변
작성한 질문수
5-K 문제 틀린 로직인가요?
작성
·
240
0
안녕하세요 큰돌선생님 매번 좋은강의와 코드 감사합니다
강의와 수업을 복습하며 문제를 다시 풀어보았는데요, 제 처음 풀이는 플러드 필을 사용하면 깔끔하게 풀 수 있을것 같아서 적용하여 풀어보았는데, 문제의 예제조차 통과하지 못하여 그냥 새롭게 큐를 계속 새로 만들어서 하는 방식으로 수정하여 통과하였습니다.
근데 첫번째 접근방법의 로직에서 틀린부분이 없다고 생각하는데 혹시 어디가 틀린것인지 봐주실 수 있으신가요?
새롭게 미세먼지가 퍼지는 부분을 큐에 계속 담는 방식을 사용하였습니다.
첫번째 틀린 코드
http://boj.kr/cdaa0817a0054c8aaa05db4a94fd4cc1
수정후 정답 코드
답변 1
1
안녕하세요 명운님 ㅎㅎ
근데 첫번째 접근방법의 로직에서 틀린부분이 없다고 생각하는데 혹시 어디가 틀린것인지 봐주실 수 있으신가요?
>> 이문제는 한턴씩 미세먼지가 퍼져나가는 것 등을 구현해야 하는 문제인데요.
c++
void go() {
int qize = q.size();
while (qize--) {
int cnt = 0;
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 < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (a[ny][nx] == -1) continue;
cnt++;
temp[ny][nx] += a[y][x] / 5;
q.push({ny, nx});
}
temp[y][x] += a[y][x] - ((a[y][x] / 5) * cnt);
q.push({y, x});
}여기서... q push를 해서 계속해서 확산을 해야할 이유가 있나요?
문제를 보시면..
미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다.
(r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.
즉, 계속해서 확산이 재귀적으로 일어나지않습니다.
근데 명운님 코드를 보시면 확산발생 -> q.push -> 다시 확산발생 이게 들어가있는 코드가 아닌가요?
이부분 때문에 틀리신 것 같습니다. ㅎ
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
아.. 이해했습니다.저 q.size를 q.size()로 봤네요...
q.push 를 한 이유는 다음 턴때 다시 미세먼지의 위치를 파악해서 q에다가 담는 로직을 생략
>> 이로직자체가 틀린 것 같습니다. 이미 변했다? 다시 변할 가능성이 있다. = 맞습니다.
그러나.
저 코드자체가 좀 문제가 있습니다.
a, b, c이렇게 되어있으면
처음에 a
그 다음에 a, b를 합니다.
근데 그 다음이 문제인데
a, b / b, a, c 이렇게 되어버립니다.
#include <bits/stdc++.h>
void go() {
int qize = q.size();
while (qize--) {
int cnt = 0;
tie(y, x) = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
...
temp[ny][nx] += a[y][x] / 5;
q.push({ny, nx});
}
temp[y][x] += a[y][x] - ((a[y][x] / 5) * cnt);
q.push({y, x});
}
memcpy(&a[0][0], &temp[0][0], sizeof(temp));
memset(&temp[0][0], 0, sizeof(temp));
a[y1][x1] = -1; a[y2][x2] = -1;
}
이 코드 자체가 지금의 y, x랑 그리고 그 다음의 ny, nx 둘다를 추가하니까요.
그래서 틀린 것 같습니다. ㅎㅎ
첫 답변이 혼란을 드려서 죄송합니다.
감사합니다.
아 제가 다시 q.push 를 한 이유는 다음 턴때 다시 미세먼지의 위치를 파악해서 q에다가 담는 로직을 생략하기 위해 그렇게 작성하였습니다.
go() 함수에서는 qsize 를 따로 정의하여 q.push를 하여도 지금 턴에는 영향을 끼치지 않고 기존 미세먼지의 수 만큼만 돌아가기 때문에 그렇게 작성하였습니다.
혹시 제가 이해하지 못하는 부분이 어디인가요?ㅜㅠ