인프런 커뮤니티 질문&답변
작성한 질문수
14502 다시금 질문드립니다..!
작성
·
150
0
http://boj.kr/840f45d321eb47839eab789e324f7551
세번째 질문.. 다시 드립니다 ㅠㅠ
combi함수에서.. 64~67라인에서 마지막에 pop_back()을 하는 이유도 이해 했습니다. 조합에서 각 재귀가 들어갈 때마다 넣고
재귀함수에서 나오면 빼서 다음 포문에서 골라서 다시 넣어야 하니까요.
다만 제가 묻고 싶은 점은..
제 문제가 로직상 틀린 점이 없다고 생각했는데 정답 처리가 안나서 어디서 오류가 나는 지를 모르겠습니다 ㅠㅠ
제가 생각한 사고 방식은 다음과 같습니다.
---
74~79 라인에서 단순히 h벡터에 0인 좌표들을 넣어놓구요..(h는 조합이 될 후보군들의 좌표를 넣어놓은 벡터)
----
combi함수로 들어가..
64~68라인에서 h벡터 에서 조합을 해서 s벡터에 좌표들을 넣습니다.(s는 세개를 조합하고 난 선정된 좌표들을 넣어놓은 벡터)
-----
31 라인에서 만약 3개의 좌표가 s벡터에 들어가면
32~36까지 visited 배열을 문제에서 준 초기 배열(== arr배열)로 초기화를 하구요.
38~40은 s벡터에 조합해둔 좌표들에 벽을 세웁니다(1로 바꿔줍니다.)
42~46에서 값이 2인 곳 즉 이미 바이러스가 있는 곳에서 dfs를 합니다.
----
17~27까지 dfs를 하는데.. 이제 해당 좌표로 들어오면 바이러스가 전염된 걸로 보고(2로 바꿔줍니다.)
4방향 중 0인 곳에만 다시 방문을 해서 dfs를 합니다.
----
48~58까지는 단순히 visited 배열 상의 안전지대 즉 값이 0인 곳을 카운팅 해서
기존의 ans와 값을 비교하여 더 큰 값을 측정합니다.
어느 라인에서 제가 실수를 해서 오답 판정을 받았을까요?
답변 1
0
오... ㅎㅎ 이제 모든 코드를 이해하시고 맞왜틀까지 오셨군요. ㅎㅎ
축하드립니다. 완섭님.
제가 주석을 달아봤습니다. 해당부분 참고해주세요. 감사합니다.
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,-1,0,1 };
int n, m;
int arr[10][10];
int visited[10][10];
vector<pair<int, int>> h;
vector<pair<int, int>> s;
int ans = 0;
void dfs(int y,int x) {
visited[y][x] = 2;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
// 왜 벽일 때의 로직이 없죠? 벽은 통과 못합니다. 바이러스.
if (visited[ny][nx] == 0) { dfs(ny, nx); }
}
}
void combi(int k) {
if (s.size() == 3) {
// visited라는 임시 배열에다가 arr 설정 good
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
visited[i][j] = arr[i][j];
}
}
// 벽 세우기 : good
for (int i = 0; i < 3; i++) {
visited[s[i].first][s[i].second] = 1;
}
// 바이러스면 퍼진다 : good
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(visited[i][j] == 2) dfs(i,j);
}
}
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == 0) temp++;
}
}
ans = max(temp, ans);
return;
}
for (int i = k; i < h.size(); i++) {
s.push_back(h[i]);
combi(k + 1);
s.pop_back();
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] == 0) h.push_back({ i,j });
}
}
combi(0);
cout << ans;
}