개인 기록장

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

map<pair<int, int>, int> houseIndex;  //row, col에서 집 index 찾아내려고 쓴 map
vector<vector<int>> board;
vector<pair<int, int>> houseVec;  //집 위치 저장하는 vector
vector<pair<int, int>> chickenVec;  //치킨집 위치 저장하는 vector
vector<vector<int>> dist;  //[치킨집 번호][집 번호] 거리
vector<int> minDist;  //각 집의 최소 치킨거리
int houseNum;  //집 갯수
int chickenNum;  //치킨집 갯수
int n, m;
int ans = 10000000000;

//동서남북
int dRow[4] = { 0,0,1,-1 };
int dCol[4] = { 1,-1,0,0 };

//범위 안에 있는지 검사
bool inRange(int row, int col) {
	if (1 <= row && row < n + 1 && 1 <= col && col < n + 1)
		return true;

	return false;
}

//치킨집 번호, 시작 치킨집 row, 시작 치킨집 col
//치킨집을 시작으로 bfs 돌려서 각 집까지의 거리 구하기
void bfs(int cnt, int row, int col) {
	queue<pair<int, int>> q;
	vector<vector<int>> distance(n + 1, vector<int>(n + 1, -1));

	q.push({ row, col });
	distance[row][col] = 0;

	while (!q.empty()) {
		int hereRow = q.front().first;
		int hereCol = q.front().second;
		int hereDist = distance[hereRow][hereCol];

		//집이라면
		if (board[hereRow][hereCol] == 1) {
			int index = houseIndex[{hereRow, hereCol}];  //row, col에서 집 index 알아내기
			dist[cnt][index] = hereDist;  //dist에 저장
		}

		q.pop();

		for (int i = 0; i < 4; i++) {
			int thereRow = hereRow + dRow[i];
			int thereCol = hereCol + dCol[i];

			if (inRange(thereRow, thereCol) && distance[thereRow][thereCol] == -1) {
				q.push({ thereRow, thereCol });
				distance[thereRow][thereCol] = hereDist + 1;
			}
		}
	}
}

//cnt번재 고를거야
void recursive(int cnt, int index, vector<int>& select) {
	if (cnt == m + 1) {
		//select에 m개

		//모든 집에대해 최소 치킨 거리 구하기
		for (int j = 0; j < houseNum; j++) {
			int tempMin = 1000000;
			for (int k = 0; k < select.size(); k++) {
				int i = select[k];  //select에서 고른 치킨집만
				tempMin = min(dist[i][j], tempMin);
			}
			minDist[j] = tempMin;
		}

		int tempAns = 0;
		for (int i = 0; i < minDist.size(); i++) {
			tempAns += minDist[i];  //각 집의 치킨 거리 더하기
		}
		ans = min(ans, tempAns);

		return;
	}

	for (int i = index; i < chickenNum; i++) {
		select.push_back(i);
		recursive(cnt + 1, i + 1, select);
		select.pop_back();
	}
}

int main() {
	scanf("%d %d", &n, &m);
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));
	
	int houseCnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 1) {
				houseVec.push_back({ i,j });
				houseIndex[{i, j}] = houseCnt;
				houseCnt++;
			}
			else if (board[i][j] == 2)
				chickenVec.push_back({ i,j });
		}
	}
	houseNum = houseVec.size();
	chickenNum = chickenVec.size();
	dist = vector<vector<int>>(chickenNum, vector<int>(houseNum));
	minDist = vector<int>(houseNum);

	//////////////////////////////////

	//치킨집 기준 bfs
	for (int i = 0; i < chickenNum; i++) {
		bfs(i, chickenVec[i].first, chickenVec[i].second);
	}

	vector<int> select;
	recursive(1,0, select);

	printf("%d", ans);
	
	return 0;
}

앞으로는 푸는데 걸린 시간도 써야지

소요 시간: 50분

치킨 집에서 bfs를 시작할지 집에서 bfs를 시작할지 고민하다가 치킨집은 최대 13개뿐이니까 치킨집에서 bfs를 시작하기로 결정

다른 분들 보니까 dfs 쓰신분도 많던데 난 아직 저 문제를 보고 dfs를 써야겠다는 생각이 안들었다.. 아직 부족하다 많이ㅜ

거리라고해서 무조건 bfs를 돌렸는데 생각해보니 각각 가중치가 있는것도 아니고 거리 공식이 있는데 왜 bfs를 돌렸을까

그냥 치킨집 m개 재귀돌리면서 뽑고 각 집에서 뽑아진 치킨집에 대해 거리 구하면 될걸 너무 어렵게 풀었다 (밑에 코드).... bfs 한번 더 연습한셈 치자

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

vector<vector<int>> board;
vector<pair<int, int>> houseVec;  //집 위치 저장하는 vector
vector<pair<int, int>> chickenVec;  //치킨집 위치 저장하는 vector
int houseNum;  //집 갯수
int chickenNum;  //치킨집 갯수
int n, m;
int ans = 10000000000;

//동서남북
int dRow[4] = { 0,0,1,-1 };
int dCol[4] = { 1,-1,0,0 };

//범위 안에 있는지 검사
bool inRange(int row, int col) {
	if (1 <= row && row < n + 1 && 1 <= col && col < n + 1)
		return true;

	return false;
}

//cnt번재 고를거야
void recursive(int cnt, int index, vector<int>& select) {
	if (cnt == m + 1) {
		//select에 m개

		vector<int> minDist(houseNum, 100000000);

		//모든 집에대해 최소 치킨 거리 구하기
		for (int j = 0; j < houseNum; j++) {
			for (int k = 0; k < select.size(); k++) {
				int i = select[k];  //select에서 고른 치킨집만
				minDist[j] = min(minDist[j], abs(houseVec[j].first - chickenVec[i].first) + abs(houseVec[j].second - chickenVec[i].second));
			}
		}

		int tempAns = 0;
		for (int i = 0; i < minDist.size(); i++) {
			tempAns += minDist[i];  //각 집의 치킨 거리 더하기
		}
		ans = min(ans, tempAns);

		return;
	}

	for (int i = index; i < chickenNum; i++) {
		select.push_back(i);
		recursive(cnt + 1, i + 1, select);
		select.pop_back();
	}
}

int main() {
	scanf("%d %d", &n, &m);
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 1) 
				houseVec.push_back({ i,j });
			else if (board[i][j] == 2)
				chickenVec.push_back({ i,j });
		}
	}
	houseNum = houseVec.size();
	chickenNum = chickenVec.size();
	
	//////////////////////////////////

	vector<int> select;
	recursive(1, 0, select);

	printf("%d", ans);
	
	return 0;
}

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> board;
int n, m, h;
int answer = 1000;

//범위 안에 있는지
bool inRange(int row, int col) {
	if (1 <= row && row < h + 1 && 1 <= col && col < 2 * n)
		return true;

	return false;
}

bool isAnswer() {
	int check = 0;
	for (int j = 1; j < 2 * n; j = j + 2) {
		//사다리 한 줄씩 확인
		int row = 1;  //처음 row부터
		int col = j;
		while (row <= h) {
			//왼쪽 가로선 확인
			if (inRange(row, col -1) && board[row][col - 1] == 1) {
				col = col - 2;  //있으면 이동
			}

			//오른쪽 가로선 확인
			else if (inRange(row, col + 1) && board[row][col + 1] == 1) {
				col = col + 2;  //있으면 이동
			}
			row++;  //밑으로도 한 칸
		}
		if (j == col) {
			check++;  //처음 시작한 곳과 끝난 곳이 같으면
		}
	}

	if (check == n)  //모두 처음 시작한 곳과 끝난 곳이 같으면
		return true;  //정답
	else
		return false;
}

//row, col에 사다리 가로 줄 놓을 수 있는가
bool isPossiblePut(int row, int col) {
	//내가 놓으려는 곳이 가로줄 첫 열이라면 연속 확인 필요 없음. 그냥 놓으려는 곳에 가로줄 없는지만 체크
	if (!inRange(row, col - 2) && board[row][col] == 0)
		return true;

	//이전 연속인가 확인
	if (inRange(row, col - 2) && board[row][col - 2] == 0 && board[row][col] == 0)
		return true;

	return false;
}

//cnt번째 할거야. row, col에 놓을거야
void recursive(int cnt, int row, int col) {
	if (isAnswer()) {
		//놓은건 cnt-1개이므로
		answer = min(answer, cnt - 1);
		return;  //최소값이니까 더 볼 필요 없음
	}

	if (cnt == 4) {
		return;
	}
	
	bool isFirst = true;
	for (int i = row; i < h + 1; i++) {
		for (int j = 2; j < 2 * n; j = j+2) {
			if (isFirst) {
				isFirst = false;
				j = col - 2;
				continue;
			}

			//i,j에 놓을 수 있다면
			if (isPossiblePut(i,j)) {
				board[i][j] = 1;  //놓기
				recursive(cnt + 1, i, j + 2);  //재귀
				board[i][j] = 0;  //원래대로
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &n, &m, &h);
	board = vector<vector<int>>(h + 1, vector<int>(2 * n, 0));
	//board의 홀수 열은 사다리 세로 줄 있는 곳 (모두 1)
	//board의 짝수 열은 사다리 가로 줄 놓을 수 있는 곳

	//가로줄
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		board[a][2 * b] = 1;
	}

	//세로줄
	for (int i = 1; i < h + 1; i++) {
		for (int j = 1; j < 2 * n; j = j + 2) {
			board[i][j] = 1;
		}
	}
	
	//////////////

	recursive(1, 1, 2);

	if (answer == 1000)  //답 없다면
		printf("-1\n");
	else
		printf("%d\n", answer);

	return 0;
}

완전탐색

사다리를 어떻게 표현할지 고민한 문제... 홀수열은 세로줄, 짝수열은 가로줄을 놓기로 하고 진행함

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int n, m;  //판 크기
int row, col, dir;  //로봇 청소기의 위치, 방향
vector<vector<int>> board;  //벽 여부
vector<vector<bool>> isClean;  //청소 여부

int dRow[4] = { -1,0,1,0 };  //북동남서
int dCOl[4] = { 0,1,0,-1 };

//범위 검사
bool inRange(int r, int c) {
	if (0 <= r && r < n && 0 <= c && c < m)
		return true;

	return false;
}

//왼쪽으로 돌리기
void rotate() {
	dir--;
	if (dir == -1)
		dir = 3;
}

//한칸 전진.
void moveForward() {
	//dir 0 1 2 3 북 동 남 서
	row = row + dRow[dir];
	col = col + dCOl[dir];
}

//한칸 후진
void moveBack() {
	//dir 0 1 2 3 북 동 남 서

	int backDir;  //후진할 방향
	if (dir == 0 || dir == 1)
		backDir = dir + 2;
	else if (dir == 2 || dir == 3)
		backDir = dir - 2;

	row = row + dRow[backDir];
	col = col + dCOl[backDir];
}

//뒤에 공간이 있는지
bool hasBackSpace() {
	int backDir;
	if (dir == 0 || dir == 1)
		backDir = dir + 2;
	else if (dir == 2 || dir == 3)
		backDir = dir - 2l;

	//뒷 부분 좌표
	int nextRow = row + dRow[backDir];
	int nextCol = col + dCOl[backDir];

	//범위를 넘거나 범위 안에 있지만 벽이면 false return
	if (!inRange(nextRow, nextCol) || board[nextRow][nextCol] == 1)
		return false;

	return true;
}

//왼쪽에 청소할 수 있는 공간이 있는지
bool hasLeftSpace() {
	int nextRow = row;
	int nextCol = col;
	if (dir == 0) {
		//북
		nextCol += -1;
	}
	else if (dir == 1) {
		//동
		nextRow += -1;
	}
	else if (dir == 2) {
		//남
		nextCol += 1;
	}
	else if (dir == 3) {
		//서
		nextRow += 1;
	}

	//범위안에 있으면서 벽도 아니고 청소도 안되어있으면 true
	if (inRange(nextRow, nextCol) && board[nextRow][nextCol] == 0 && !isClean[nextRow][nextCol])
		return true;

	return false;
}

int main() {
	scanf("%d %d", &n, &m);
	scanf("%d %d %d", &row, &col, &dir);

	board = vector<vector<int>>(n, vector<int>(m));
	isClean = vector<vector<bool>>(n, vector<bool>(m, false));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &board[i][j]);
		}
	}

	//////////////////

	int answer = 0;
	bool isOver = false;

	while (true) {
		//1) 현재 위치 청소
		isClean[row][col] = true;
		answer++;

		int check = 0;
		for (int i = 0; i < 4; i++) {
			if (hasLeftSpace()) {
				rotate();  //회전
				moveForward();  //전진
				
				break;  //1)로 넘어가기
			}

			if (!hasLeftSpace()) {
				//왼쪽에 청소할 공간 없다면
				check++;
				rotate();
			}

			if (check == 4) {
				//네방향 다 없어
				if (!hasBackSpace()) {
					//뒤쪽 방향이 벽
					isOver = true;  //while 탈출
					break;  
				}

				moveBack();  //한칸 후진
				check = 0;
				i = -1;  //다시 네방향 처음부터 검사
			}
		}

		if (isOver)
			break;
	}

	printf("%d\n", answer);
	return 0;
}

시뮬

주의해야 할 점: 청소기 방향에 따라서 오른쪽 왼쪽 앞 뒤 좌표값을 다르게 줘야한다

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Fish {
public:
	int row;  //물고기 있는 행
	int col;  //물고기 있는 열
	int size;  //물고기 사이즈

	//canEatFishVec에 있는것만 값 있음
	int fishVecindex;  //fishVec에서는 index가 몇번인지
	int distance;  //아기상어와의 거리

	Fish(int r, int c, int s) {
		row = r;
		col = c;
		size = s;
	}
};

int n;
vector<vector<int>> board;
vector<Fish> fishVec;  //전체 물고기
vector<Fish> canEatFishVec;  //먹을 수 있는 물고기
int sharkRow, sharkCol, sharkSize, sharkEatNum;  //아기상어 행, 열, 크기, 현재 먹은 물고기 갯수
int time = 0;  //시간. 답

//동서남북
int dRow[4] = { 0,0,1,-1 };
int dCol[4] = { 1,-1,0,0 };

void bfs() { 
	//아기상어로부터의 거리 구하기
	vector<vector<int>> distance(n, vector<int>(n, -1));
	queue<pair<int, int>> q;

	q.push({ sharkRow, sharkCol });
	distance[sharkRow][sharkCol] = 0;

	while (!q.empty()) {
		int hereRow = q.front().first;
		int hereCol = q.front().second;
		int hereD = distance[hereRow][hereCol];
		q.pop();

		for (int i = 0; i < 4; i++) {
			int thereRow = hereRow + dRow[i];
			int thereCol = hereCol + dCol[i];

			//범위안이고 내가 지나갈 수 있고 간 적 없다면
			if (0 <= thereRow && thereRow < n &&
				0 <= thereCol && thereCol < n &&
				board[thereRow][thereCol] <= sharkSize &&
				distance[thereRow][thereCol] == -1) {
				distance[thereRow][thereCol] = hereD + 1;
				q.push({ thereRow, thereCol });
			}
		}
	}

	//먹을 수 있는 물고기 체크
	//먹을 수 있다 <=> 크기가 상어 크기 이하 && 막혀있지 않음 (distance != -1)
	for (int i = 0; i < fishVec.size(); i++) {
		if (fishVec[i].size < sharkSize && distance[fishVec[i].row][fishVec[i].col] != -1) {
			//크기가 아기상어보다 작고 먹으러갈 수 있다면
			canEatFishVec.push_back(fishVec[i]);
			canEatFishVec.back().fishVecindex = i;  //방금 넣은 애의 index
			canEatFishVec.back().distance = distance[fishVec[i].row][fishVec[i].col];  //방금 넣은 애의 dist
		}
	}
}

//canEatFishVec의 몇번째 index를 먹으러 갈건지
void eat(int canEatFishVecIndex) {
	board[sharkRow][sharkCol] = 0; //상어가 이동했으니까 원래 상어 자리는 빈 자리로
	sharkRow = canEatFishVec[canEatFishVecIndex].row;  //상어는 물고기 자리로 이동
	sharkCol = canEatFishVec[canEatFishVecIndex].col;
	time += canEatFishVec[canEatFishVecIndex].distance;  //한칸 이동에 1초 걸리므로
	board[sharkRow][sharkCol] = 9;  //물고기 먹었으니까 그 자리에는 상어가

	sharkEatNum++; //물고기를 먹는다
	if (sharkSize == sharkEatNum) {  //현재 상어 크기만큼 물고기 먹었으면
		sharkSize++;  //상어 크기 + 1
		sharkEatNum = 0; 
	}

	//먹은 물고기 fishVec에서 제거
	//canEatFishVec은 while마다 새로 구하기 때문에 여기선 없애줄 필요 없음
	int fishVecindex = canEatFishVec[canEatFishVecIndex].fishVecindex;
	fishVec.erase(fishVec.begin() + fishVecindex);
}

int close() {
	//다음에 먹을 물고기의 canEatFishVec에서의 index return
	priority_queue<pair<pair<int, int>, pair<int, int>>> pq;  //-거리, -row, -col, canEatFishVec에서의 index
	for (int i = 0; i < canEatFishVec.size(); i++) {
		pq.push({ {-1 * canEatFishVec[i].distance, -1 * canEatFishVec[i].row}, { -1 * canEatFishVec[i].col, i} });
	}

	int ret = pq.top().second.second;  //index
	return ret;
}

int main() {

	scanf("%d", &n);
	board = vector<vector<int>>(n, vector<int>(n));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &board[i][j]);

			if (1 <= board[i][j] && board[i][j] <= 6) {
				Fish f(i, j, board[i][j]);
				fishVec.push_back(f);
			}

			else if (board[i][j] == 9) {
				sharkRow = i;
				sharkCol = j;
				sharkSize = 2;
				sharkEatNum = 0;
			}
		}
	}

	////////////////////////////

	
	while (true) {
		canEatFishVec.clear();  //매번 먹을 수 있는 물고기 새로 구하기
		bfs();  //먹을 수 있는 물고기 목록 구하기. row, col, distance, fistVecIndex

		if (canEatFishVec.empty()) {
			break;  //먹을 수 있는 물고기가 없다면
		}
		
		if (canEatFishVec.size() == 1) {
			eat(0);  //먹을 수 있는 물고기가 한마리라면 그 한마리 먹기. 하나니까 인덱스 무조건 0
		}
		else {
			int eatIndex = close();  //가장 가까운 물고기가 canEatFishVec에서 몇번 index인지
			eat(eatIndex);  //그 물고기 먹으러 간다
		}
	}

	cout << time;

	return 0;
}

거리 -> bfs

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;
vector<vector<int>> board;
vector<pair<int, int>> virus;  //바이러스 좌표
int ans = -1;

//동서남북
int dRow[4] = { 0, 0, 1, -1 };
int dCol[4] = { 1, -1, 0, 0 };

//cnt번째 벽을 row, col에 세울거야
void recursive(int cnt, int row, int col) {
	if (cnt == 4) {
		//기저
		
		//바이러스 위치를 시작으로 bfs 돌리기
		vector <vector<bool>> discover(n, vector<bool>(m, false));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 1)
					discover[i][j] = true;  //벽이면 bfs 돌릴 때 가면 안되니까 discover true로 해주고 안가게
			}
		}

		//바이러스 위치를 시작으로 bfs 돌리기
		for (int v = 0; v < virus.size(); v++) {
			//bfs 시작 위치 (바이러스 위치)
			int startRow = virus[v].first;
			int startCol = virus[v].second;

			queue<pair<int, int>> q;
			q.push({ startRow, startCol });
			discover[startRow][startCol] = true;

			while (!q.empty()) {
				int hereRow = q.front().first;
				int hereCol = q.front().second;
				q.pop();

				//동서남북
				for (int i = 0; i < 4; i++) {
					int thereRow = hereRow + dRow[i];
					int thereCol = hereCol + dCol[i];

					//범위내이고 
					if (0 <= thereRow && thereRow < n &&
						0 <= thereCol && thereCol < m && 
						!discover[thereRow][thereCol]) {
						//범위안에 있고 큐에 들어간적없으면
						q.push({ thereRow, thereCol });
						discover[thereRow][thereCol] = true;
					}
				}
			}
		}

		//바이러스가 퍼지지 않은 곳 세기
		int tempAns = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!discover[i][j])
					tempAns++;
			}
		}

		ans = max(ans, tempAns);

		return;
	}

	vector<vector<int>> tempBoard = board;  //원상태로 돌리기 위해

	bool isFirst = true;
	for (int i = row; i < n;  i++) {
		for (int j = 0; j < m; j++) {
			//전 재귀에서 본 좌표 다음부터 보기 위해서
			if (i == row && isFirst) {
				isFirst = false;
				j = col;
				if (j >= m)
					continue;
			}

			if (board[i][j] == 0) {
				//빈칸이면 벽 세우기
				board[i][j] = 1;
				recursive(cnt + 1, i, j + 1);
				board = tempBoard;  //원 상태로 돌리기 (벽 없애기)
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	board = vector<vector<int>>(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &board[i][j]);

			if (board[i][j] == 2) {
				//바이러스라면
				virus.push_back({ i,j });
			}
		}
	}

	//////////////////////////

	recursive(1, 0, 0);
	cout << ans;

	return 0;
}

완전탐색 + BFS (또는 DFS)

Visual studio에서 테스트케이스 돌렸을 때 너무 오래걸리길래 시간 줄여볼 방법 생각해보다가 그냥 제출했는데 제출됨.... 컴퓨터 과부하 걸렸나 좀 쉬어줘야지

둘 다 풀 수 있으니까 BFS 할까 DFS 할까 고민했는데 DFS 쓰면 재귀함수가 두개가 되는게 꼴보기 싫어서 그냥 BFS....

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> board;
vector<int> dice(7, 0); 
int n, m, x, y, k;

bool inRange(int row, int col) {
	if (0 <= row && row < n && 0 <= col && col < m)
		return true;

	return false;
}

void rollDice(int dir) {
	if (dir == 1) {
		//동
		int temp1 = dice[3];
		dice[3] = dice[1];
		dice[1] = dice[4];
		dice[4] = dice[6];
		dice[6] = temp1;
	}
	else if (dir == 2) {
		//서
		int temp = dice[4];
		dice[4] = dice[1];
		dice[1] = dice[3];
		dice[3] = dice[6];
		dice[6] = temp;
	}
	else if (dir == 3) {
		//북
		int temp = dice[2];
		dice[2] = dice[1];
		dice[1] = dice[5];
		dice[5] = dice[6];
		dice[6] = temp;
	}
	else if (dir == 4) {
		int temp = dice[6];
		dice[6] = dice[5];
		dice[5] = dice[1];
		dice[1] = dice[2];
		dice[2] = temp;
	}
}

int main() {
	scanf("%d %d  %d %d %d", &n, &m, &y, &x, &k);

	board= vector<vector<int>>(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &board[i][j]);
		}
	}

	vector<int> command(k);
	for (int i = 0; i < k; i++) {
		scanf("%d", &command[i]);
	}

	////////////////////////////////

	int currentCommand;

	for (int i = 0; i < k; i++) {
		int nextRow = y;
		int nextCol = x;

		currentCommand = command[i];
		

		if (currentCommand == 1) {  //동
			nextCol = x + 1;
		}
		else if (currentCommand == 2) {  //서
			nextCol = x - 1;
		}
		else if (currentCommand == 3) {  //북
			nextRow = y - 1;
		}
		else if (currentCommand == 4) {  //남
			nextRow = y + 1;
		}

		if (inRange(nextRow, nextCol)) {
			//갈 수 있으면
			rollDice(currentCommand);  //주사위 굴리기

			y = nextRow;
			x = nextCol;

			if (board[y][x] == 0) {
				board[y][x] = dice[6];
			}
			else {
				dice[6] = board[y][x];
				board[y][x] = 0;
			}
			printf("%d\n", dice[1]);
		}
		else {  //갈 수 없으면 다시 돌려놓기
			
		}
	}


	return 0;
}

주사위를 각 방향으로 굴렸을 때 어떤 모양이 되는지 잡는게 포인트!

중학교떄부터 전개도 이런거 너무 못하고 싫어해서 이런 문제 너무 싫다...... 이거 풀때도 육면체 모양 지우개 굴려가면서 함..

1. 실수했던 부분

1) 범위를 넘어가도 주사위는 굴렸음.. 문제에 "주사위는 지도의 바깥으로 이동시킬 수 없다. 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안 된다."라로 확실히게 명시 되어있었는데 왜 그랬지ㅠ 문제를 잘 읽자....

2) 게시판 겨우 찾아가면서 해결했는데 입력을 x y 순서로 받는게 아니라 y x 순서로 받아야한단다.... 문제를 보면 r c / x y 이렇게 각각 r는 x에, c는 y에 대응되는데 문제의 입력에 써있는 x y랑 내 문제 속 x y랑 반대였다

아마 이런걸 코테 중에 마주쳤다면 평생 모르지 않았을까싶음...ㅋ

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int main() {
	long long answer = 0;
	int n, b, c;
	scanf("%d", &n);
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	scanf("%d %d", &b, &c);

	//////////////////////////

	//1. 총감독관 한명씩 배치
	vector<int>::iterator iter;

	for (int i = 0; i < a.size(); i++) {
		a[i] -= b;
		answer++;
	}

	//2. 부감독관 배치
	for (int i = 0; i < a.size(); i++) {
		if (a[i] <= 0)
			continue;

		if (a[i] % c != 0) {
			answer += (a[i] / c) + 1;
		}
		else {
			answer += a[i] / c;
		}
	}

	cout << answer << endl;

	return 0;
}

int 아닌 long long

int는 21억까지만!

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <algorithm>

using namespace std;

int answer = -1;

void printVec(vector<vector<int>> board) {
	for (int i = 0; i < board.size(); i++) {
		for (int j = 0; j < board[i].size(); j++) {
			printf("%3d ", board[i][j]);
			//cout << board[i][j] << "   ";
		}
		cout << endl;
	}
	cout << endl;
}

vector<vector<int>> move(char dir, vector<vector<int>> board) {
	int n = board.size();
	if (dir == 'u') {
		//위
		//일단 합칠 수 있는 블럭 합쳐
		for (int col = 0; col < n; col++) {
			for (int row = 0; row < n - 1; row++) {
				if (board[row][col] != 0) {
					//해당 col에서 밑으로 내려가다가 가장 먼저 만나는 0이 아닌 수
					int tempRow = row;
					while (true) {
						tempRow++;
						if (tempRow >= n)  //범위검사
							break;

						if (board[tempRow][col] != 0) {
							if (board[tempRow][col] != board[row][col]) {
								row = tempRow-1;
								break;
							}
							if (board[tempRow][col] == board[row][col]) {
								board[row][col] = board[row][col] * 2;
								board[tempRow][col] = 0;
								row = tempRow;
								break;
							}
						}
					}
				}
			}
		}
		//빈칸 없이 밀어
		for (int col = 0; col < n; col++) {
			for (int row = 0; row < n - 1; row++) {
				if (board[row][col] == 0) {
					//해당 col에서 밑으로 내려가다가 가장 먼저 만나는 0이 아닌 수
					int tempRow = row;
					while (true) {
						tempRow++;
						if (tempRow >= n)  //범위검사
							break;

						if (board[tempRow][col] != 0) {
							board[row][col] = board[tempRow][col];
							board[tempRow][col] = 0;
							break;
						}
					}
				}
			}
		}
	}

	else if (dir == 'd') {
		//아래
		//일단 합칠 수 있는 블럭 합쳐
		for (int col = 0; col < n; col++) {
			for (int row = n-1; row > 0; row--) {
				if (board[row][col] != 0) {
					//해당 col에서 위로 올라가다가 가장 먼저 만나는 0이 아닌 수
					int tempRow = row;
					while (true) {
						tempRow--;
						if (tempRow < 0)  //범위검사
							break;

						if (board[tempRow][col] != 0) {
							if (board[tempRow][col] != board[row][col]) {
								row = tempRow + 1;
								break;
							}
							if (board[tempRow][col] == board[row][col]) {
								board[row][col] = board[row][col] * 2;
								board[tempRow][col] = 0;
								row = tempRow;
								break;
							}
						}
						
					}
				}
			}
		}
		//빈칸 없이 밀어
		for (int col = 0; col < n; col++) {
			for (int row = n - 1; row > 0; row--) {
				if (board[row][col] == 0) {
					//해당 col에서 위로 올라가다가 가장 먼저 만나는 0이 아닌 수
					int tempRow = row;
					while (true) {
						tempRow--;
						if (tempRow < 0)  //범위검사
							break;

						if (board[tempRow][col] != 0) {


							board[row][col] = board[tempRow][col];
							board[tempRow][col] = 0;
							break;
						}
					}
				}
			}
		}
	}

	else if (dir == 'l') {
		//왼쪽
		//일단 합칠 수 있는 블럭 합쳐
		for (int row = 0; row < n; row++) {
			for (int col = 0; col < n - 1; col++) {
				if (board[row][col] != 0) {
					//해당 roow에서 오른쪽으로 가다가 가장 먼저 만나는 0이 아닌 수
					int tempCol = col;
					while (true) {
						tempCol++;
						if (tempCol >= n)  //범위검사
							break;

						if (board[row][tempCol] != 0) {
							if (board[row][tempCol] != board[row][col]) {
								col = tempCol-1;
								break;
							}
							if (board[row][tempCol] == board[row][col]) {
								board[row][col] = board[row][col] * 2;
								board[row][tempCol] = 0;
								col = tempCol;
								break;
							}
						}
						
					}
				}
			}
		}
		//printVec(board);
		//빈칸 없이 밀어
		for (int row = 0; row < n; row++) {
			for (int col = 0; col < n - 1; col++) {
				if (board[row][col] == 0) {
					//해당 roow에서 오른쪽으로 가다가 가장 먼저 만나는 0이 아닌 수
					int tempCol = col;
					while (true) {
						tempCol++;
						if (tempCol >= n)  //범위검사
							break;


						if (board[row][tempCol] != 0) {
							
							board[row][col] = board[row][tempCol];
							board[row][tempCol] = 0;
							break;
						}
					}

				}
			}
		}
		//printVec(board);
	}

	else if (dir == 'r') {
		//오른쪽
		//일단 합칠 수 있는 블럭 합쳐
		for (int row = 0; row < n; row++) {
			for (int col = n-1; col > 0; col--) {
				if (board[row][col] != 0) {
					//해당 roow에서 왼쪽으로 가다가 가장 먼저 만나는 0이 아닌 수
					int tempCol = col;
					while (true) {
						tempCol--;
						if (tempCol < 0)  //범위검사
							break;

						if (board[row][tempCol] != 0) {
							if (board[row][tempCol] != board[row][col]) {
								
								col = tempCol+1;
								break;
							}
							if (board[row][tempCol] == board[row][col]) {
								board[row][col] = board[row][col] * 2;
								board[row][tempCol] = 0;
								col = tempCol;
								break;
							}
						}
						
					}
				}
			}
		}
		//빈칸 없이 밀어
		for (int row = 0; row < n; row++) {
			for (int col = n - 1; col > 0; col--) {
				if (board[row][col] == 0) {
					//해당 roow에서 왼쪽으로 가다가 가장 먼저 만나는 0이 아닌 수
					int tempCol = col;
					while (true) {
						tempCol--;
						if (tempCol < 0)  //범위검사
							break;

						if (board[row][tempCol] != 0) {

							board[row][col] = board[row][tempCol];
							board[row][tempCol] = 0;
							break;
						}
					}

				}
			}
		}
	}

	int maxVal = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			maxVal = max(maxVal, board[i][j]);
		}
	}
	answer = max(answer, maxVal);
	return board;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<vector<int>> board(n, vector<int>(n));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &board[i][j]);
		}
	}

	map < vector<vector<int>>, int> dist;
	queue < vector<vector<int>>> q;
	q.push(board);
	dist[board] = 0;
	//cout << endl;
	while (!q.empty()) {
		vector<vector<int>> here = q.front();
		int hereDist = dist[here];
		q.pop();

		if (hereDist == 5)
			break;

		//인접 board 생성
		vector<vector<int>> temp;
		temp = move('u', here);
		if (dist.count(temp) == 0) {
			q.push(temp);
			dist[temp] = hereDist + 1;
		}

		temp = move('d', here);
		if (dist.count(temp) == 0) {
			q.push(temp);
			dist[temp] = hereDist + 1;
		}

		temp = move('l', here);
		if (dist.count(temp) == 0) {
			q.push(temp);
			dist[temp] = hereDist + 1;
		}

		temp = move('r', here);
		if (dist.count(temp) == 0) {
			q.push(temp);
			dist[temp] = hereDist + 1;
		}
	}

	cout << answer;

	return 0;
}

BFS 이용함. 코드 진짜 길고 못생겼어...

1. 실수 했던 부분

1) 진짜 어이없게 영어 소문자 l를 한글 모음 ㅣ로...

2) 숫자 중간에 0이 있는 경우를 고려하지 않았음. 바로 맞닿아 있을 때에만 합침

=> 해결 방법: 민 방향 쪽부터 반대 방향쪽으로 보면서 최초의 0이 아닌 다른 수와 같으면 합침

3) 진짜 이거때문에 몇시간 헤맸는데 bfs 돌리면서 종료 조건 (최대 5번 이동) 검사를 while문 끝에 함

내가 지금 움직인 횟수가 5번째면 while문 탈출하도록

근데 만약 큐 내부에 있는 것의 distance(이동횟수)만 적으면 (front) 4 4 4 4 4 로 있고 제일 front 쪽 4를 꺼내서 한번 더 이동시키면 아직 검사할 게 뒤에도 많은데 5번째로 움직였으니까 바로 탈출했음.. 끝까지 검사를 안했음

=> 해결 방법: bfs 종료 조건을 while 문 앞에 둬서 내가 지금 꺼낸게 5번 이동한 상태면 break. 왜냐면 이미 이동을 5번 한게 pop() 된거면 뒤에 있는 것도 이미 다 5번 이상 한거임.. 문제에서 최대 5번 이동이므로 의미 없다....

교훈: 방향 표시할때 영어 소문자 안쓰고 대문자 쓸래... U D R L 그리고 bfs 종료 조건은 항상 앞에서 검사해야겠다.

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