급하게임개발

https://www.acmicpc.net/problem/1600

#include <iostream>
#include <queue>
using namespace std;

int arr[200][200];
bool visited[200][200][31] = { false }; // visited[row][col][사용한 말 이동 횟수]
int dx[4] = { 0, 0, -1, 1 };            // 상하좌우 이동
int dy[4] = { 1, -1, 0, 0 };
int hx[8] = { -2, -2, 2, 2, -1, -1, 1, 1 }; // 말(나이트) 이동
int hy[8] = { 1, -1, 1, -1, 2, -2, 2, -2 };

int main() {
    int k, w, h;
    cin >> k >> w >> h;
    // h행, w열의 배열 입력 (문제에서 h가 행의 개수, w가 열의 개수임)
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> arr[i][j];
        }
    }

    // (현재 행, 현재 열)와 (이동 횟수, 사용한 말 이동 횟수)
    queue< pair< pair<int, int>, pair<int, int> > > bfsQ;
    bfsQ.push({ {0, 0}, {0, 0} });
    visited[0][0][0] = true;

    int minMoves = -1;
    while (!bfsQ.empty()) {
        pair< pair<int, int>, pair<int, int> > cur = bfsQ.front();
        bfsQ.pop();
        int x = cur.first.first;
        int y = cur.first.second;
        int moveCount = cur.second.first;
        int horseUsed = cur.second.second;

        // 목적지: (h-1, w-1)
        if (x == h - 1 && y == w - 1) {
            minMoves = moveCount;
            break;
        }

        // 4방향 이동 (상, 하, 좌, 우)
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                continue;
            if (arr[nx][ny] == 1)
                continue;
            if (!visited[nx][ny][horseUsed]) {
                visited[nx][ny][horseUsed] = true;
                bfsQ.push({ {nx, ny}, {moveCount + 1, horseUsed} });
            }
        }

        // 말 이동 (나이트 이동) 처리 (남은 말 이동 횟수가 있을 경우)
        if (horseUsed < k) {
            for (int i = 0; i < 8; i++) {
                int nx = x + hx[i];
                int ny = y + hy[i];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w)
                    continue;
                if (arr[nx][ny] == 1)
                    continue;
                if (!visited[nx][ny][horseUsed + 1]) {
                    visited[nx][ny][horseUsed + 1] = true;
                    bfsQ.push({ {nx, ny}, {moveCount + 1, horseUsed + 1} });
                }
            }
        }
    }

    cout << minMoves;
    return 0;
}

이 문제는 조금 어려운 BFS 였다 어렵다기 보다는 isVisited를 선언할 때 3차원 배열로 할수 있음이 있었다
즉 말움직임을 k번사용해서 방문했을 때의 대한 값을 저장해놓았다 그리고 해당 문제는 bfs 이기에 먼저 도착했을 경우 해당 값은 이미 방문처리가 되었기 때문에 방문 최소 횟수 를 저장해놓을 필요는 없는 문제였다

https://www.acmicpc.net/problem/16947

이 문제도 어느 게임회사 코테에 나왔던 문제였다 코테풀기전에 이문제를 풀었다면 좋았었을텐데 지금에서야 접했다

이문제는 사이클이 하나만 있다고 가정하고 그래프릍 탐색해서 순환 구조를 파악하는 문제이다 
첫 번째로 사이클을 탐색하는 규칙은 자신으로 왔을떄 자신의 이전 노드들을 저장하고 있는다 그리고 만약에 다음노드를 방문했을때 이노드가 방문되어있고 이노드에 저장되어있던 노드가 지금 노드와 다르다면 이노드는 순환구조를 만든 노드라고 파악한다

이에 대한 코드는 아래와 같다

void findCycle(int cur) {
	isVisited[cur] = true;
	for (int i = 0; i < vertex[cur].size(); i++) {
		if (hasCycle)
			return;
		int next = vertex[cur][i];
		if (isVisited[next]) {
			if (next != pre[cur]) {
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
	
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}

이렇게 dfs를 통해 방문 한 노드에 대해서 이전노드들을 검사해준다 그후 순환 노드가 파악이되었으면 pre 배열을 통해 이전 노드들을 파악해서 cycle로 체크를 해준다


이제 cycle로부터 각 노드들이 얼만큼 떨어져 있는 지 계산한다

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			isVisited[i] = true;
			q.push({ i,0 });
		}
	}

	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();

		isVisited[cur] = true;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i];
			if (isVisited[next])
				continue;
			dist[next] = dis + 1;
			q.push({ next, dis + 1 });
		}
	}
}

bfs를 통해 판별한다

전체 코드는 아래와같다

#include <iostream>
#include <vector>
#include <queue>
#include<cstring>
using namespace std;
bool isVisited[3001];
int pre[3001];
bool cycle[3001];
int dist[3001];
vector<int> vertex[3001];
int n;
bool hasCycle;

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 1; i <= n; i++) {
		if (cycle[i]) {
			isVisited[i] = true;
			q.push({ i,0 });
		}
	}

	while (!q.empty()) {
		int cur = q.front().first;
		int dis = q.front().second;
		q.pop();

		isVisited[cur] = true;

		for (int i = 0; i < vertex[cur].size(); i++) {
			int next = vertex[cur][i];
			if (isVisited[next])
				continue;
			dist[next] = dis + 1;
			q.push({ next, dis + 1 });
		}
	}
}
void findCycle(int cur) {
	isVisited[cur] = true;
	for (int i = 0; i < vertex[cur].size(); i++) {
		if (hasCycle)
			return;
		int next = vertex[cur][i];
		if (isVisited[next]) {
			if (next != pre[cur]) {
				cycle[cur] = true;
				hasCycle = true;
				while (cur != next) {
					cycle[pre[cur]] = true;
					cur = pre[cur];
				}
				return;
			}
	
		}
		else {
			pre[next] = cur;
			findCycle(next);
		}
	}
}
int main() {
	cin >> n;
	int tmp1, tmp2;
	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2;
		vertex[tmp1].push_back(tmp2);
		vertex[tmp2].push_back(tmp1);
	}
	findCycle(1);
	memset(isVisited, false, 3001);
	bfs();
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << ' ';
	}
}

https://www.acmicpc.net/problem/1939

이 문제는 bfs에 이분탐색을 통한 적절한 값 찾기 이다 
처음에는 갈수있는 경로별 최댓값을 구하려 했으나 시간초과가 났다 당연한 얘기다

자 일단 이코드는 bfs를 통해 특정 노드에서 노드로 가는 경우의 수를 모두 탐색하는데 이때 우리는 무게를 계속 정해주고 해당 무게가 특정 다리의 cost를 넘어가면 이후 탐색의 값을 좀더 줄여 나가는 방식으로 진행한다 도착점에 도착하면 그이후로 탐색하지않는다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector < pair < int , int >> v[100001];
bool isVisited[100001];
int maxNum = 1000000000;
int bfs(int from, int to) {
	int lo = 1;
	int hi = maxNum;
	int mid;
	int ans;
	while (lo <= hi) {
		mid = (lo + hi) / 2;

		for (int i = 0; i < n+1; i++) {
			isVisited[i] = false;
		}

		queue<int> q;

		q.push(from);
		isVisited[from] = true;
		bool canMore = false;

		while (!q.empty()) {
			int node = q.front();
			q.pop();

			if (node == to) {
				canMore = true;
				break;
			}

			for (int i = 0; i < v[node].size(); i++) {
				int next = v[node][i].first;
				int cost = v[node][i].second;
				if (isVisited[next])
					continue;
				if (mid > cost)
					continue;
				isVisited[next] = true;
				q.push(next);
			}
		}

		if (canMore) {
			lo = mid + 1;
			ans = mid;
		}
		else {
			hi = mid - 1;
		}
	}
	return ans;

}
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	int a, b, c;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;

		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}

	int from, to;
	cin >> from >> to;
	int ans = bfs(from, to);
	cout << ans;

}

https://www.acmicpc.net/problem/17135

이 문제는 그냥 여러개 섞어놓은 문제이다 병사를 배정하는것은 조합으로 dfs로 풀면 되고 
병사들이 몬스터를 잡는건 bfs로 풀면된다 조합에대한 모든것을 bfs함으로 브루트포스이기도 하다 사실이문제는 단지 기본적인 알고리즘 여러개를 섞어놓은것이다
주의할 점은 bfs를 할때

int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};

이 순서대로 해야한다 bfs가 거리가 가까운거는 보장하지만 왼쪽 탐색을 하기위해서는 해당 인덱스를 따라 해야지 왼쪽부터 탐색한다
또한 탐색하자마자 바로 0으로 바꾸지말고 중복으로 한 몬스터를 때릴수 있으므로 4로 체크하고 이후에 0으로 바꾼다

#include <iostream>
#include <stdlib.h>
#include <queue>
using namespace std;
int originArr[16][15];
int copyArr[16][15];
int N, M, D;
int goX[3] = { 0,-1,0};
int goY[3] = { -1,0,1};
int maxNum;
bool isVisited[16][15] = { 0, };
bool AllDie() {
	bool isDie = true;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (copyArr[i][j] == 1)
				isDie = false;
		}
	}
	return isDie;
}
void CopyOrigin() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			copyArr[i][j] = originArr[i][j];
		}
	}
}
bool CanGo(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M ) {
		return true;
	}
	else {
		return false;
	}
}
void downEnemy() {
	for (int i = N-1 ; i > 0; i--) {
		for (int j = 0; j < M; j++) {
			copyArr[i][j] = copyArr[i - 1][j];
			if (copyArr[i][j] == 4)
				copyArr[i][j] = 0;
		}
	}
	for (int i = 0; i < M; i++) {
		copyArr[0][i] = 0;
	}
}
int bfs(int armyX, int armyY) {
	queue<pair<int, pair<int, int>>> ArmyQ;
	ArmyQ.push({ 0,{armyX,armyY} });
	int count = 0;
	while (!ArmyQ.empty()) {
		int curX = ArmyQ.front().second.first;
		int curY = ArmyQ.front().second.second;
		int cost = ArmyQ.front().first;
		ArmyQ.pop();
		if (cost > D)
			break;
		if (copyArr[curX][curY] == 4) {
			break;
		}
		if (copyArr[curX][curY] == 1) {
			copyArr[curX][curY] = 4;
			count += 1;
			break;
		}

		for (int i = 0; i < 3; i++) {
			int nextX = curX + goX[i];
			int nextY = curY + goY[i];
			if (CanGo(nextX, nextY)) {
				ArmyQ.push({ cost + 1,{nextX,nextY} });
			}
		}
	}
	return count;
}
void dfs(int start, int count) {
	if (count == 3) {// 병사를 3명 다배치 했을 경우
		CopyOrigin();
		int num = 0;
		while (!AllDie()) {
			for (int i = 0; i < M; i++) {
				if (copyArr[N][i] == 3) {
					num += bfs(N, i);
				}
			}
			downEnemy();
		}
		maxNum = max(num, maxNum);
	}
	
	else {
		for (int i = start+1; i < M; i++) {
			originArr[N][i] = 3;
			dfs(i, count + 1);
			originArr[N][i] = 2;
		}
	}
}
int main() {
	cin >> N >> M >> D;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> originArr[i][j];
		}
	}
	for (int i = 0; i < M; i++) {
		originArr[N][i] = 2;
	}
	for (int i = 0; i < M; i++) {
		originArr[N][i] = 3;
		dfs(i, 1);
		originArr[N][i] = 2;
	}
	cout << maxNum;
}

https://www.acmicpc.net/problem/2589

이 문제의 경우 브루트 포스긴 하나 모든 경우의 수에 대해 bfs를 이용해서 푸는 문제였다 bfs를 브루트포스하여 푸는 문제니 부르트포스 문제일 수도 있고 bfs 문제일 수도 있다 이문제의 경우 bfs를 구현할 줄 알면 큰  문제가 없다 본인의 경우 2%의  오류가 났었는데 해당 이유는 처음 bfs를 실행할 때 해당 위치가 'W'인지를 검사 하지 않아서 발생 했었다

#include<iostream>
#include<queue>
using namespace std;
int n, m;
char arr[50][50];
int isVisited[50][50] = { 0, };
int maxLength=0;
queue<pair<int, int>>bfsQ;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
bool canGo(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < m && !isVisited[x][y] && arr[x][y]=='L')
		return true;
	else
		return false;
}
void bfs(int sx, int sy) {
	bfsQ.push({ sx,sy });
	isVisited[sx][sy] = 1;
	while (!bfsQ.empty()) {
		int sx = bfsQ.front().first;
		int sy = bfsQ.front().second;
		int distance = isVisited[sx][sy];
		bfsQ.pop();
		for (int i = 0; i < 4; i++) {
			if (canGo(sx + dx[i], sy + dy[i])) {
				bfsQ.push({sx + dx[i],sy + dy[i]});
				isVisited[sx + dx[i]][sy + dy[i]] = distance + 1;
			}
		}
	}
}
int getMaxValue() {
	int maxValue=0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			maxValue=max(maxValue, isVisited[i][j]);
		}
	}
	return maxValue-1;
}
void InitIsVisited() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			isVisited[i][j] = 0;
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (canGo(i, j)) {
				bfs(i, j);
				maxLength = max(maxLength, getMaxValue());
				InitIsVisited();
			}
		}
	}
	cout << maxLength;
}

https://www.acmicpc.net/problem/2234

이 문제의 경우 bfs 문제이다 

우리가 구해야 할 답은 총 3개다
1 번과 2번은 그냥 우리가 아는 bfs 로 영역의 최대 크기와 영역의 갯수를 구해주면된다
3번은 내가 있는 방을 기준으로 4방의 방에서 벽을 뚫는다고 가정하고 풀었다 그후 모든 방에서 상하좌우방을 뚫었을 때 진행할수 있으면 진행 하도록 코드를 작성 하였다

#include <iostream>
#include<bitset>
#include <queue>
#include <cstring>
using namespace  std;
int arr[50][50];
bool isVisited[50][50];
int n, m;
int maxCnt = 1;
int xi[4] = { 0,1,0,-1 };
int yi[4] = { 1,0,-1,0 };
queue<pair<int, int>> bfsq;
bool canGo(int x, int y , int z) {
	if (x >= 0 && x < m && y >= 0 && y < n && !isVisited[x][y]) {
		if (arr[x][y] & (1 << z)) {
			return false;
		}
		else
			return true;
	}
	return false;
}
bool canGo(int x, int y) {
	if (x >= 0 && x < m && y >= 0 && y < n ) {
		return true;
	}
	return false;
}

void bfs(int startX, int startY) {
	bfsq.push({ startX,startY });
	isVisited[startX][startY] = true;
	int cnt = 1;
	while (!bfsq.empty()) {
		int col = bfsq.front().first;
		int row = bfsq.front().second;
		bfsq.pop();
		for (int i = 0; i < 4; i++) {
			if (canGo(col + xi[i], row + yi[i],i)) {
				bfsq.push({ col + xi[i] , row + yi[i] });
				isVisited[col + xi[i]][row + yi[i]] = 1;
				cnt += 1;
				if (maxCnt < cnt)
					maxCnt = cnt;
			}
		}
	}
}
int main() {
	int roomCnt=0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (isVisited[i][j])
				continue;
			roomCnt += 1;
			bfs(i, j);
		}
	}
	cout << roomCnt << endl;
	cout << maxCnt << endl;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++){
			for (int k = 0; k < 4; k++) {
				if (canGo(i + xi[k], j + yi[k]) && (arr[i + xi[k]][j + yi[k]] &(1<<k))) {
					memset(isVisited, 0, sizeof(isVisited));
					arr[i + xi[k]][j + yi[k]] ^= (1 << k);
					bfs(i, j);
					arr[i + xi[k]][j + yi[k]] |= (1 << k);
				}
			}
		}
	}

	cout << maxCnt;
}

https://www.acmicpc.net/problem/16236

이 문제는 솔직히 설명이 겁나 불친절하다 

정확히 이문제는 핵심이 나를 기준으로 나보다 크기가 작고 같은 거리에 있는 물고기 들은 위에에서 왼쪽부터 오른쪽 까지 검사하고 내려와서 왼쪽부터 오른쪽 까지 검사하면서 이 순으로 탐색을 하는 거였다.
단 위에를 듣고 BFS  이동방향을 1,0 ->0,-1 ->0,1 ->-1,0 이렇게 만 하면 안풀린다

while (!bfsQ.empty()) {
		
				otherX = bfsQ.front().second.first;
				otherY = bfsQ.front().second.second;
				otherCost = bfsQ.front().first;
				if (CanEat(otherX, otherY) && otherCost<=cost) {
					if (otherX < startX) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
					else if (otherX == startX && startY>otherY ) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
				}

핵심은 이부분이다 내가 물고기를 먹을 수있는 지역으로 갔을 때 현재 큐에  들어와 있는 것중 나보다 거리가 작거나 같고 행의 값이  위에 있거나 혹은 행이 같다면 열값이 더 먼저인 애를 찾아서 거기를 가야한다 이에 의해 필자는 행을 검사에서 위에있으면 해당 행으로 탐색지점을 바꿔줬고 같다면 열값이 더 작은 쪽으로 옮겨줬다

#include <iostream>
#include <queue>
using namespace std;
int n;
int arr[20][20] = { 0, };
bool isVisited[20][20];
int fishSize = 2;
int eatFish = 0;
int cnt = 0;
queue<pair<int,pair<int, int>>>  bfsQ;

bool CanEat(int x, int y) {
	if (arr[x][y]>0&&arr[x][y] < fishSize) {
		return true;
	}
	return false;
}
bool canGo(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < n && !isVisited[x][y] && (CanEat(x, y) || arr[x][y] == 0 || arr[x][y]==fishSize))
		return true;
	else
		return false;
}

void Bfs(int x, int y) {
	bfsQ.push({ cnt,{x,y} });
	arr[x][y] = 0;
	int startX, startY, cost;
	int otherX, otherY, otherCost;
	while (!bfsQ.empty()) {
		startX = bfsQ.front().second.first;
		startY = bfsQ.front().second.second;
		cost = bfsQ.front().first;
		bfsQ.pop();
		if (CanEat(startX, startY)) {
			cnt += cost;
			while (!bfsQ.empty()) {
		
				otherX = bfsQ.front().second.first;
				otherY = bfsQ.front().second.second;
				otherCost = bfsQ.front().first;
				if (CanEat(otherX, otherY) && otherCost<=cost) {
					if (otherX < startX) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
					else if (otherX == startX && startY>otherY ) {
						startX = otherX;
						startY = otherY;
						otherCost = cost;
					}
				}

				bfsQ.pop();
				
			}
			bfsQ.push({ 0, {startX, startY}});
			eatFish += 1;
			if (eatFish == fishSize) {
				fishSize += 1;
				eatFish = 0;
			}
			arr[startX][startY] = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					isVisited[i][j] = false;
				}
			}
			isVisited[startX][startY] = true;
			cost = 0;
		}

		if (canGo(startX-1,startY)) {
			bfsQ.push({ cost + 1,{startX -1,startY}});
			isVisited[startX - 1][startY] = 1;
		}
		if (canGo(startX, startY-1)) {
			bfsQ.push({ cost + 1,{startX ,startY - 1} });
			isVisited[startX][startY-1] = 1;
		}
		if (canGo(startX , startY+1)) {
			bfsQ.push({ cost + 1,{startX ,startY + 1} });
			isVisited[startX][startY + 1] = 1;
		}
		if (canGo(startX+1 , startY)) {
			bfsQ.push({ cost + 1,{startX + 1,startY} });
			isVisited[startX + 1][startY] = 1;
		}
	}

}
int main() {
	cin >> n;
	int startIdxCol, startIdxRow;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				startIdxCol = i;
				startIdxRow = j;
			}
		}
	}

	Bfs(startIdxCol, startIdxRow);
	cout << cnt;
}

https://school.programmers.co.kr/learn/courses/30/lessons/250136

이 문제는 간단한 문제인줄 알고 건드렸다가 2시간을 날릴 정도로 고생한 문제이다 
일단 이 문제의경우 딱 봤을 때 BFS를 사용하는거는 확실 해 보이지만 매번 시추할 때 마다 BFS를 돌리면 효율성 검사에서 점수가 떨어지게 된다 이에 이문제는 BFS를 이용해서 뽑아낸 데이터를 어떤 자료 구조에 넣어 사용하는 지가 매우 중요한 문제이다

#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
int directionX[4] = { 1, 0, -1, 0 };
int directionY[4] = { 0, 1, 0, -1 };
int isVisited[501][501] = { 0, };
map<int, int> sizeOfOil;
int sizeOfLandX;
int sizeOfLandY;
int areaNum = 1;
vector<vector<int>> oilMap;
void BFS(int startX, int startY ) {
    int tmp = 0;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    oilMap[startX][startY] = areaNum;
    isVisited[startX][startY] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        tmp++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
                oilMap[nextX][nextY] = areaNum;
                isVisited[nextX][nextY] = 1;
                q.push({ nextX,nextY });
            }
        }
    }
    sizeOfOil[areaNum] = tmp;
    areaNum++;
   
}
int solution(vector<vector<int>> land) {
    int answer = 0;
    oilMap = land;
    sizeOfLandX = land.size(); //열의 길이
    sizeOfLandY = land[0].size(); //행의 길이

    for (int i = 0; i < sizeOfLandX; i++) {
        for (int j = 0; j < sizeOfLandY; j++) {
            if (isVisited[i][j] == false && land[i][j] == 1) {
                BFS(i, j);
            }
        }
    }

    for (int j = 0; j < sizeOfLandY; j++) {
        set<int> oilSet;
        int sumOfOil=0;
        for (int i = 0; i < sizeOfLandX; i++) {
            oilSet.insert(oilMap[i][j]);
        }
        set<int>::iterator iter;
        for (auto it : oilSet) {
            sumOfOil += sizeOfOil[it];
        }
        answer = max(answer, sumOfOil);
    }

    return answer;
}

일단 이 문제의 경우 내가 블로그에 기존에 올렸던 BFS보다 간단 하다 원래는 Direction을 일일히 내가 정해줬었는데 이를 배열에 넣어 간단하게 보이게 했다. 코드 가독성이 올라가니 확실히 디버깅 효율이 올라갔다

자 일단 이문제의 핵심로직은 BFS로 구해놓은 영역의 유전의 크기를 영역별로 들고 있어야 한다 이를 위해 위 코드에

void BFS(int startX, int startY ) {
    int tmp = 0;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    oilMap[startX][startY] = areaNum;
    isVisited[startX][startY] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        tmp++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX >= 0 && nextX < sizeOfLandX && nextY >= 0 && nextY < sizeOfLandY && isVisited[nextX][nextY] == false && oilMap[nextX][nextY]>0) {
                oilMap[nextX][nextY] = areaNum;
                isVisited[nextX][nextY] = 1;
                q.push({ nextX,nextY });
            }
        }
    }
    sizeOfOil[areaNum] = tmp;
    areaNum++;
   
}

BFS 부분에서sizeOfOil에 저장해 주었다 여기서 sizeOfOil은 맵 자료형이다 맵자료형은 map<int,int>이렇게 사용했을 때 맨앞에 오는 값은 Key로서 두번쨰 오는 값은 value로 써 작용합니다.
즉 map<key, value> 의 형태로 각각의 해당하는 자료형을 넣어주면 됩니다 .

이 문제에서는 Map의 저장해놓은 데이터를 순환하여 찾아와야 하기 때문에

for (auto iter = m.begin() ; iter !=  m.end(); iter++)
{
	cout << iter->first << " " << iter->second << endl;
}
cout << endl;

의 형태와

for (auto iter : m) {
	cout << iter.first << " " << iter.second << endl;
}

의 형태의 두가지 형태로 map을 순환 할 수 있습니다.
이에 필자는 두번째 형태로 사용하였습니다. 

이렇게 Map형태로 저장해놓은 데이터에서 우리는 land 배열에 새로줄에서 만나는 areaNum들을 set에 넣어줍니다.
Set은 마찬가지로 중복되는 자료를 넣으면 넣지 않기 때문에 areaNum을 최대 1번씩만 넣을 수 있습니다
이에 set.insert를 이용해서 각 세로줄에 있는 유전의 areaNum을 넣습니다.

그후 이를 순회하면서 areaNum을 통해 세로줄에 있는 해당 유전에 크기를 더하여 최대값을 출력합니다