[HackerRank] DFS: Connected Cell in a Grid

문제 링크 - https://www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem

 

코드

int maxRegion(vector<vector<int>> grid) 
{
    int length = grid[0].size();
    int height = grid.size();
    vector<bool> heightsVisited(length, false);
    vector<vector<bool>> visited(height, move(heightsVisited));
    using IntPair = pair<int, int>;

    queue<IntPair> findQueue;
	int maxCount = 0;

    for (int y = 0; y < height; ++y)
    {
        vector<int> arr = grid[y];
        bool bFound = false;
		int count = 0;

        for (int x = 0; x < length; ++x)
        {
            int num = arr[x];

            if (num == 1)
            {
                if (!visited[y][x])
                {
                    findQueue.push({ x, y });
                    ++count;
					visited[y][x] = true;
                    bFound = true;
                    break;
                }
            }
        }

		while (findQueue.size() > 0)
		{
			auto numPair = findQueue.front();
			findQueue.pop();
			int x = numPair.first;
			int y = numPair.second;

			vector<IntPair> surroundPairs = { {x - 1, y - 1}, {x, y - 1}, {x + 1, y - 1}, {x - 1, y}, {x + 1, y}, {x - 1, y + 1}, {x, y + 1}, {x + 1, y + 1 } };
			for (const auto surroundPair : surroundPairs)
			{
				int xSurround = surroundPair.first;
				int ySurround = surroundPair.second;

				if (xSurround >= 0 && xSurround < length && ySurround >= 0 && ySurround < height)
				{
					if (visited[ySurround][xSurround])
					{
						continue;
					}

					if (grid[ySurround][xSurround] == 1)
					{
						findQueue.push({ xSurround, ySurround });
						++count;
					}

					visited[ySurround][xSurround] = true;
				}
			}
		}

		if (count > maxCount)
		{
			maxCount = count;
		}
    }

    return maxCount;
}

 

풀이 - bfs, dfs 도 아닌 스스로 생각한 방식으로 풀어봤다. 해커 랭크에서 푼 bfs 문제(https://haewoneee.tistory.com/196)랑 비슷하게 큐를 이용했다. 이중 for 문을 돌며 그리드의 모든 요소를 검색한다. 맨 처음, 큐에 값이 1 인 인덱스를 넣는다. 그 후 그 인덱스와 연결된 모든 경우를 찾아본다. 찾은 연결된 인덱스 갯수가 현재까지 가장 큰 연결된 인덱스 갯수보다 크면 변경한다. 그리드의 다음 요소를 똑같은 방식으로 검색하는데, 다만 이미 방문했던 요소는 건너뛴다. 건너뛰는 이유는 해당 요소는 다른 요소와 연결되었기 때문에 방문 처리를 했을 것이고, 해당 요소와 연결된 인덱스 덩어리는 이미 계산된 것이기 때문이다.

 

후기 - 다음에는 재귀를 이용하는 정석적인 dfs 방식으로 풀어봐야지