[구름] 현대모비스 예선-주차시스템 C++

 

https://level.goorm.io/exam/152115/%ED%98%84%EB%8C%80%EB%AA%A8%EB%B9%84%EC%8A%A4-%EC%98%88%EC%84%A0-%EC%A3%BC%EC%B0%A8%EC%8B%9C%EC%8A%A4%ED%85%9C/quiz/1

구름LEVEL

 

풀이

 

간단한 bfs 탐색문제

처음엔 dfs로 풀었는데, 시간초과로 인해 bfs로 재풀이

 

한 칸 한 칸 탐색하며 방문한적 없고 값이 1이 아닌 좌표들에 대해 bfs 실행 >> 해당 구역의 점수 반환

반환된 점수를 max 함수를 이용하여 maxVal에 저장

값 출력

 

 

 

int n;	// 행
int m;	// 열
int maxVal;	// 구역 점수 중 가장 높은 점수
vector<vector<int>> input;	// 입력값을 저장할 2차원 벡터
int visit[2001][2001] = {};	// bfs 탐색 시 방문 여부
int xdir[4] = {0, 1, 0, -1};	// nextX 를 위한 배열
int ydir[4] = {1, 0, -1, 0};	// nextY 를 위한 배열


int bfs(int x, int y) {

	queue<pair<int, int>> q;	// bfs를 위한 queue, x, y값 한번에 저장하기 위한 pair 컨테이너
	q.push(make_pair(x, y));	// bfs의 시작좌표 (x, y)를 q에 삽입 
	visit[x][y] = 1;			// 그 후, (x, y)를 방문했는 의미로 1로 값 변경
	int score = 0;				// 구역의 점수를 담을 score 변수 선언

	// q가 비어있지 않다면 반복 >> 이어져 있는 구역이 있담면
	while (!q.empty()) {

        // 현재 탐색하고 있는 x, y 의 좌표값을 curX, curY에 담고
        // queue 맨 앞의 좌표값을 pop()
        int curX = q.front().first;
		int curY = q.front().second;
		q.pop();
        
        
		// 현재 좌표의 값이 0이라면, 즉 비어있는 구역이라면 score + 1
		if (input[curX][curY] == 0)
			score += 1;
            
        // 현재 좌표의 값이 2이라면, 비어있지만 장애인 구역이라면 score - 2
		else if (input[curX][curY] == 2)
			score -= 2;


		// for문으로 현재 좌표의 상, 하, 좌, 우 4방향에 인접한 좌표 탐색
		for (int i = 0; i < 4; i ++) {

			// 인접한 좌표의 x, y 값
			int nextX = curX + xdir[i];
			int nextY = curY + ydir[i];

			// 만약 인접 좌표가 전체 주차장 크기를 벗어나지 않으면서 아직 방문하지 않은 구역이라면
			if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < m && visit[nextX][nextY]==0 && input[nextX][nextY]!=1) {
				
                // 방문으로 표시하고
                visit[nextX][nextY] = 1;
                
                // 좌표를 queue에 삽입
				q.push(make_pair(nextX, nextY));
			}
		}
	}
    
    
    // queue가 비어 반복문이 종료되면 하나의 구역 탐색 완료
    // score 에 그 구역의 점수를 담아 return
	return score;

}


int main() {
	
    // 주차장 구역의 크기 입력
	cin >>n >> m;

	// 반복문을 통해 주차장의 각 좌표값들을 input vector 컨테이너에 저장
	for (int i = 0; i < n; i++) {

		vector<int> temp;
		for (int j = 0; j < m; j++) {

			int value;
			cin >> value;
			temp.push_back(value);
		}
		input.push_back(temp);
	}

	// maxVal 초기화
	maxVal = 0;


	// 주차장 정보가 담겨있는 input vector를 한칸한칸 탐색하며 bfs 실행 >> 하나의 구역 점수 계산
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			
            // 만약 현재 좌표가 아직 방문하지 않았고 값이 1이라면
			if (visit[i][j] == 0 && input[i][j] !=1) {
            
				// maxVal와 bfs를 통해 나온 한 구역의 점수를 비교하여 큰 쪽을 maxVal에 저장
				maxVal = max(maxVal, bfs(i, j));
			}

		}
	}

	// 결과 출력
	cout<< maxVal << endl;
}