글 읽기 - (C++) 답은 맞았는데 궁금한게 있습니다.

pch1623 4년 전 0

dfs 함수에서 for문을이용하여 4번을 돌렸는데 제가 이거 실수로 돌렸다가 발견하고 for문을 빼니까 오답뜨고 그래서 다시 for문을 넣었는데 정답 처리가 되더라구요
아무리 생각해봐도 for문이 왜 필요한건지 이해가 잘 가지않습니다 ..

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>


using namespace std;
bool visited[30][30] = { 0 };
int map[30][30] = { 0 };
int ans[650];
int N, node = 0, cnt = 0;
void dfs(int, int);
void dfsall();

void dfsall() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (!visited[i][j] && map[i][j]) {
				dfs(i,j);
				
				ans[node] = cnt;
				node++;
				cnt = 0;
			}
		}
	}
}
void dfs(int a,int b) { 
	if (visited[a][b]) return;
		
	visited[a][b] = 1;
	cnt++;
	for (int i = 1; i <= 4; i++) { //for 문이 왜 필요한건지. . .ㅠㅠ
	
			if (!visited[a + 1][b] && map[a + 1][b]) 
				dfs(a + 1, b);
			else if (!visited[a - 1][b] && map[a - 1][b]) 
				dfs(a - 1, b);
			else if (!visited[a][b + 1] && map[a][b + 1]) 
				dfs(a, b + 1);
			else if (!visited[a][b - 1] && map[a][b - 1])
				dfs(a, b - 1);
	
			
		}
	
	
}

int main() {
	
	cin >> N;
	for(int i = 1;i<=N;i++){
		for (int j = 1; j <= N; j++) {
			
			int b = 0;
			scanf("%1d", &b);
			map[i][j] = b;
					   
		}
	}
	dfsall();
	sort(ans, ans + node);
	cout << node << "\n";
	for (int i = 0; i < node; i++) {
		cout << ans[i] << "\n";
	}

}

if (!visited[a + 1][b] && map[a + 1][b])
dfs(a + 1, b);
else if (!visited[a - 1][b] && map[a - 1][b])
dfs(a - 1, b);
else if (!visited[a][b + 1] && map[a][b + 1])
dfs(a, b + 1);
else if (!visited[a][b - 1] && map[a][b - 1])
dfs(a, b - 1);

이부분 왜 else if로 하셨어요???????

전부 독립된 if로 넣으셔야죠

pch1623 4년 전 0

//djm03178 죄송합니다 for문 범위를 고쳤어요 ㅠㅠ 고치넉내면 정답이라구나옵니다 ..

//왜 독립된 if 로 넣어야되는건지 알수 있을까요?? 단지가 어차피 붙어있는거면은 결국 다연결되지 않나요 ? ?

djm03178 4년 전 1

주변에 있는 칸들을 모두 방문해봐야 하는데 이렇게 하면 인접한 방향 한 군데로밖에 가보질 않습니다.

shg9411 4년 전 1

for문으로 하실 땐 보통 [[-1,0],[0,-1],[1,0],[0,1]] 이런 식으로 배열에 저장해놓고 접근할 때 사용하고

지금 올리신 코드처럼 푸실 경우에는 for문을 없애고 독립된 if문으로 진행합니다.

풀이 방식이 조금 섞여있는 듯한 느낌이네요

pch1623 4년 전 0

모두들 감사합니다 조금 이해가 되었네요 ㅎㅎ

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

문제

문제

출처

ICPC

(C++) 답은 맞았는데 궁금한게 있습니다.

pch1623 4년 전 0

djm03178 4년 전 1

meringueee 4년 전 1

pch1623 4년 전 0

//djm03178 죄송합니다 for문 범위를 고쳤어요 ㅠㅠ 고치넉내면 정답이라구나옵니다 ..

djm03178 4년 전 1

shg9411 4년 전 1

pch1623 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말