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

안녕하세요 대기업님 ㅎㅎ

너무 좋네요.

int h, w, dy = 0, dx = 1;
char a[104][104];

dy, dx도 잘 하셨구요.

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (a[i][j] == 'c' && visited[i][j] == -1) bfs(i, j);
		}
	}

방문한 정점은 다시 방문하지 않게 하신 것도 좋습니다.

좋은 코드인 것같습니다.

그러나 답안코드보다 효율적이지는 않습니다.

			if(a[i][j] == 0){ 
				int cnt = 1;
				while(a[i][j + 1] == -1){
					a[i][j + 1] = cnt++;
					j++;
				} 
			}

답안 코드는 while 반복문을 기반으로 로직을 처리하고 있는데요.

BFS를 하게 되면

void bfs(int y, int x) {
	queue<pair<int, int>> q;
	visited[y][x] = 0;
	q.push({y, x});

이렇게 기본적으로 queue하나, visited배열 하나가 더 필요하기 때문에 효율적이라고 보기에는 어렵습니다

다만, 좋은 코드라고 할 수 있는게 그런 자료구조가 막 그렇게 많이 필요한 것도 아니고 차이가 막 그렇게 크지는 않아서요. 깔끔하고 좋습니다.

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴이에요.

문제 링크를 확인해보니, 트리의 경로를 찾는 문제인 것 같습니다. BFS로 풀이하셨다고 하셨는데, BFS는 그래프에서 최단 경로를 찾는 데에 많이 사용되는 알고리즘입니다. 따라서, 트리에서도 효율적으로 작동할 수 있어요.

BFS 알고리즘은 너비 우선 탐색을 수행하여 그래프의 모든 노드를 탐색하는 방식입니다. 큐(Queue) 자료구조를 활용하여 구현되며, 현재 노드와 인접한 노드들을 차례로 방문하고 큐에 넣는 방식으로 동작합니다. 이를 통해 트리의 루트에서 시작하여 레벨 순서대로 탐색하면서 경로를 찾을 수 있습니다.

따라서, BFS를 사용하여 트리의 경로를 찾는 것은 효율적인 방법이라고 할 수 있어요. 하지만 문제마다 최적의 알고리즘은 다를 수 있으므로, 다른 방식도 고려해보시는 것이 좋을 거예요.

이번 문제에서 BFS를 사용한 풀이에 대한 자세한 내용은 링크를 통해서 직접 확인해보시면 도움이 될 것 같아요.

더 궁금한 점이 있으시면 언제든지 물어보세요. 결과에 대한 답변이 도움이 되었으면 좋겠어요. 감사합니다.