3-J 주난의 난 이 코드는 어떤가요??

안녕하세요 밍링님 ㅎㅎ

와 이제 골드 푸시는군요 ㅎㅎ 너무 좋네요 ㅎㅎ

앞으로도 꾸준히 하시면 더 어려운 문제들을 풀 수 있으실거에요!!

꾸준히만 해주세요 ㅎㅎ

코드 리뷰는 다음과 같습니다.

	while(1){
		memset(visited, 0, sizeof(visited));
		go(xa, ya);

지금 보시면 visited 를 매번 초기화 -> 처음 지점부터 계속해서 DFS를 하고 있습니다.

이부분이 좀 비효율적입니다. 예를 들어

a -> b -> c -> d

라고 정점이 있다라고 했을 때

a -> b

a -> b -> c

a -> b -> c -> d

이렇게 왔던 정점들을 다시 방문하고 있기 때문이죠. ㅎㅎ

queue 2개를 사용하면

이를 a -> b -> c -> d 이렇게 차근차근 하면서 정점을 중복탐색하지 않게 할 수 있습니다.

다만 잘하신점은요 ㅎㅎ

	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 || visited[ny][nx]) continue;
		if(arr[ny][nx] == 1) {
			v.push_back({ny, nx});
			continue;
		}

만났을 때 벡터에 넣고 continue를 하는 것은 매우 잘하셨습니다.

void go(int y, int x){
	visited[y][x] = 1;
	if(arr[y][x] == 3){
		flag = false;
		return;
	}

정답이 될 부분을 0와 1, 2 아닌 값을 놓은 점, flag부분도 좋습니다.

그외 초기값 선언도 좋았습니다.

int N, M, xa, ya, xb, yb, cnt = 0;
bool flag = true;
int arr[304][304], visited[304][304];
vector<pair<int, int>> v;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

다만, cnt를 전역변수로 선언하면 0으로 자동초기화가 되니 해당 부분은

int N, M, xa, ya, xb, yb, cnt;
bool flag = true;
int arr[304][304], visited[304][304];
vector<pair<int, int>> v;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

이렇게 하셔도 됩니다. ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변