코딩무식자 전공생

문제 출처: https://www.acmicpc.net/problem/16637

풀이

1. 연산자갯수와 숫자의 갯수를 각각의 배열에 담는다.

길이가 최대 19이므로 연산자9개, 피연산자 10개까지 나올 수 있다. 피연산자의 개수는 index1, 연산자의 갯수는 index2가 된다. 

내 풀이는 연산자기준으로, 연산자를 모두쓰게되면 계산 종료후 최댓값을 갱신한다.

2. 괄호쳐서 계산하는 것 잘 이해하기(괄호 치는 것만으로

대충 괄호를 쳐서 계산하는것과 괄호를 치지않고 쭉 계산해나가는 식을 작성해야함은 알 수 있다.  

괄호를 안치고 계산하는 연산은 아래 코드처럼, 연산후, dfs를 계속 돌리면된다. 

//앞에서부터 계산하기
	int res = func(sum, num[cnt + 1],op[cnt]);
	//dfs돌려서 확인하기(더 계산할 수 있는지)
	dfs(res, cnt + 1);

괄호를 쳐서 계산하는연산을 보자. 

1+2*3 일 때 괄호를 치려면, 일단 연산자가 최소 2개는 있어야한다.( 1+2 꼴일때는 괄호치는것과 안치는것 결과값같음)

따라서 1+(2*3)꼴이 되게하려면 현재 사용되고있는 연산자+1 인덱스의 연산자가 존재할 때 계산해야한다.

즉, 현재 cnt=0이라 op[cnt]=='+'인데, 1+(2*3)처럼 괄호를 치려면, cnt+1(op[cnt+1]=='*')가 아직 사용되지않았을 때다.

그리고나서 2*3을 구한뒤(a), 1과 a를 더해주면 1+(2*3)을 계산하게된다. 괄호안치는 연산 1+2*3은 이미 위의 코드로 잘 계산되고있다.

주의할 것은 b(1+ (2*3)을 계산한 값)를 구하는 func함수의 인자 순서다.

1+(2*3)일 때, (2*3)+1가 아니라 1+(2*3)이다. 계산을 괄호식부터 할 뿐이다. 주의하자. 똑같은 얘기가 아니다.

즉, 순서를 주의해야한다.

예를들어 1-9-9일 때, func함수의 인자를 (sum,a)가 아닌 (a, sum)으로 바꾸면 1-(9-9)가 아닌 (9-9)-1가 되버려서 값이 달라져버린다.  

따라서, 인자는 sum뒤에 a가 나와야한다. (a뒤에 sum이 나오게되면안됨)

그리고, 잔실수 할수 있는 부분인데, func함수의 첫번째 인자는 num[cnt]이 아닌 sum이다.

1+(2*3)일 떄, 처음 계산할 때만 생각하면 sum=1이고 num[cnt]=1 이라 똑같은 값이라고 생각할 수 있는데, 그렇게되면 아래 식이 잘못된 값이 된다.

1+2*3+5*7일 떄를 보자.

만약 func의 첫번째 인자를 num[cnt]로 작성해버리면, 1+(2*3)=7까지 계산후 7+(5*7)이 아닌, 3+(5*7)이 된다. 즉, 누적된값을 유지해야한다.

위에서 길게 얘기한 것들을 코드로 작성하면된다.

코드

#include<iostream>
#include<string>
using namespace std;
int n;
string s;
int num[10],index1, index2, max_val = -100;
char op[10];
void dfs(int sum, int cnt);
int func(int a, int b, char c);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		//숫자면 숫자배열에저장
		if (i % 2 == 0) {
			num[index1] = s[i] - '0';
			index1++;
		}
		else {
			op[index2] = s[i];
			index2++;
		}
	}
	dfs(num[0], 0);
	cout << max_val << '\n';
}
void dfs(int sum, int cnt)
{
	//모든 연산자를 사용하게됐을 때는 종료
	if (cnt == index2)
	{
		if (max_val < sum)
			max_val = sum;
		return;
	}
	//앞에서부터 계산하기
	int res = func(sum, num[cnt + 1],op[cnt]);
	//dfs돌려서 확인하기(더 계산할 수 있는지)
	dfs(res, cnt + 1);
	//괄호를 쳐서 계산하기
	//만약 계산할 연산자가 아직 남았으면 계산하기
	if (cnt + 1 < index2)
	{
		//1+2*3+5일 떄 1+(2*3)+5하는 과정
		int a = func(num[cnt + 1], num[cnt + 2], op[cnt + 1]);
		//조심!) func의 1,2번쨰 인자 순서바꾸면 틀림
		//조심!)func의 첫번째인자는 num[cnt]가 아님
		int b = func(sum, a, op[cnt]);
		//+5계산하기위해 2칸 건너뜀(+:0, *:1, +:2)
		dfs(b, cnt + 2);
	}
}
int func(int a, int b, char c)
{
	if (c == '+')return a + b;
	else if (c == '-')return a - b;
	else if (c == '*')return a * b;
	else
		exit(1);
}

결과

문제 출처: https://www.acmicpc.net/problem/15685

풀이

1. dx[4]와 dy[4]는 문제에서 주어진대로 선언해야한다.(막 선언하면안됨)

0:오른쪽 1:위 2:왼쪽 3:아래 이므로 , dx[4]={1,0,-1,0}, dy[4]={0,-1,0,1}

2. 규칙을 못찾겠다면 예제1,힌트1을 참고한다.

<규칙>
d =0 시작 기준,

0세대 : 0

1세대 : 0 /1

2세대 : 0 1 /2 1

3세대 : 0 1 2 1 /2 3 2 1

-----------------3세대 까지는 N세대: N-1세대 + N-1세대의 요소의 역순 +1

4세대 : 0 1 2 1 2 3 2 1 / 2 3 0 3 2 3 2 1

규칙을 못 찾겠거나 3세대까지의 규칙이 4세대이상부터도 똑같이 적용될 걸 의심하는 분들은 예제1과 힌트1을 참고하여 1~3세대규칙을찾고,

4세대부터는 N세대 : N-1세대 + (N-1세대의 요소의 역순 +1) %4 가 됨을 이해한다.

3. 규칙을 찾았다면 직접 그려본다(예제1과 힌트1이있으니 직접 예제1을 그려본다.)

문제에서 사각형의 갯수를 구하라고했는데, 언뜻 보면 뭔소린지 이해가 안 갈 수 있다. 예제1만봐도 사각형이 3개 있으니 3개아닌가?싶을 수 있다.

직접 그려보면 아래 그림처럼 어떤정점에서 칠해진좌표상에서 주어진 순서(0오->1위->2왼->3아래)대로1*1사각형을 그릴 수 있는 정점을 구하는 것임을 알 수 있다.

4. 그대로 구현하면된다. 

N-1세대를 이용해서 N세대를 구하고, 그래프상에서 힌트1처럼 입력된 드래곤커브들을 그려서 정점을 체크한다.

좌표가 각각 1세대:2개, 2세대:4개, 3세대: 8개, 4세대 :16개....순으로 이어지므로 아래처럼 작성하면 될 것 같다.

주의 할것은 좌표가 0~100까지이므로 배열선언시 크기를 100*100이아닌 101*101로 선언해야한다.

for (int i = 0; i < g; i++)
		{
			int len = v.size() - 1;
			for (int j = len; j >= 0; j--)
			{
				v.push_back((v[j] + 1) % 4);
			}
		}

코드

#include<iostream>
#include<vector>
using namespace std;
int n, x, y, d, g, ans;
int map[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		vector<int>v;
		cin >> x >> y >> d >> g;
		map[y][x] = 1;
		v.push_back(d);
		for (int i = 0; i < g; i++)
		{
			int len = v.size() - 1;
			for (int j = len; j >= 0; j--)
			{
				v.push_back((v[j] + 1) % 4);
			}
		}
		for (int i = 0; i < v.size(); i++)
		{
			//세대들의 정점을 칠한다.
			y = y + dy[v[i]];
			x = x + dx[v[i]];
			map[y][x] = 1;
		}
	}
	for (int i = 0; i < 100; i++)
	{
		for (int j = 0; j < 100; j++)
		{
			if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1])
				ans++;
		}
	}
	cout << ans << endl;
	
}

결과

문제 출처: https://www.acmicpc.net/problem/16235

풀이

나무의 위치와 나무의 나이, 특정 좌표의 나무의 갯수를 2차원벡터로 표현할 수 있으면 나머지는 구현문제입니다.

나무의 갯수: v.[i][j].size()

나무의 나이: v[i][j][k]

나무의 위치: i,j 

그리고 문제를 읽으실 때 주의하셔야 할게, 

입력받는 배열과 양분이 5로 채워져있는 배열은 문제만 보면 어떤차이인지 의미가 모호할 수 있으므로 양분증감량을 계산할 때 주의하셔야합니다.

**이 풀이는 180ms가 나오는데 풀이법에 따라 100ms,50ms, 심지어 0ms가 나오는 방법들도 있기 때문에 그런 코드들을 참고하는것도 좋을 것 같습니다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int  yb[10][10], a[10][10];
int dy[8] = {-1,0,1,-1,1,-1,0,1 };
int dx[8] = {-1,-1,-1,0,0,1,1,1 };
int n, m, k;
//해당위치의 나무의 나이를 저장하기위해서 벡터
vector<int>v[10][10];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
			yb[i][j] = 5;
		}
	}
	for (int i = 0; i < m; i++)
	{
		int y, x, z;
		cin >> y >> x >> z;
		v[y - 1][x - 1].push_back(z);
	}
	for (int i = 0; i < k; i++)
	{
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
			{
				//봄 여름
				//나무가 있을 떄만
				if (v[y][x].size())
				{
					int dead_tree = 0;
					vector<int>temp;
					sort(v[y][x].begin(), v[y][x].end());
					for (int num = 0; num < v[y][x].size(); num++)
					{
						int age = v[y][x][num];
						//양분이 나이보다 작으면 탈출
						if (yb[y][x] >= age)
						{
							yb[y][x] = yb[y][x] - age;
							temp.push_back(age + 1);
						}
						//탈출하되 여름에 죽은게 양분으로 변하므로
						else
						{
							dead_tree = dead_tree+age / 2;
						}
					}
					//비우고 새롭게 나이먹은 나무들을 다시 담음
					v[y][x].clear();
					for (int num = 0; num < temp.size(); num++)
						v[y][x].push_back(temp[num]);
					
					yb[y][x] += dead_tree;
				}
			}
		}
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
			{
				//나무가 있는 좌표에대해서만
				if (v[y][x].size())
				{
					for (int i = 0; i < v[y][x].size(); i++)
					{
						int age = v[y][x][i];
						if (age % 5 == 0)
						{
							for (int dis = 0; dis < 8; dis++)
							{
								int ny = y + dy[dis];
								int nx = x + dx[dis];
								if (nx >= 0 && ny >= 0 && nx < n && ny < n)
								{
									//인접한 칸에 나이1인 나무 생김
									v[ny][nx].push_back(1);
								}
							}
						}
					}
				}
			}
		}
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
			{
				yb[y][x] += a[y][x];
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			ans += v[i][j].size();
		}
	}
	cout << ans << '\n';
}

결과

문제 출처: https://www.acmicpc.net/problem/14500

대충 어렇게 코드를짜겠다고 생각했으나 구현을 못해서 구글링을 하여 도움을 얻은 문제입니다.

https://jaimemin.tistory.com/623 글을 참조했습니다.

풀이

제가 생각하는 구현에 있어서 가장 중요한 부분은

1. 백트래킹기법을 쓸줄아느냐?(대충 이해하고 넘어가니 구현할 때 손도못댑니다.)

2. ㅗ,ㅜ,ㅏ,ㅓ의 도형 모양과 다른 테트로미노 도형의 모양의 차이가 무엇인지 아느냐?(dfs의 깊이가 다름을 관찰했나?)

3. 1,2번을 관찰하고 정확히 구현할줄 아는가?

이 3가지라고생각합니다. 

구현에 있어서 중요한 것은  ㅗ,ㅜ,ㅏ,ㅓ의 모양은 다른 모양들과 dfs깊이가 다르므로 따로 처리해주고, 나머지 모양은 모양과 상관없이 

시작점부터 일반적인dfs를 돌려주면 된다는 것입니다.(4번째 탐색했을 때 함수를 종료하면됩니다.) 모든 범위에서 탐색하므로 모든 모양들에 대해 탐색하기때문입니다.

그리고, ㅗ,ㅜ,ㅏ,ㅓ를 처리해줄 때 범위의 조건을 정확히 작성해야합니다. 이게 의외로 까다롭습니다. test case는 다 맞는데 게시판에있는 반례를 입력하니 범위가 이상해서 다른 답들이 나왔습니다.

사실 많이 허무하잖아요. 자신있게 풀었는데 반례때문에 그 문제가 통째로 틀리게되는거니깐....자기가 스스로 몇개의 경우를 만들어서 더 돌려보는 습관을 가져야겠습니다. 

마지막으로, 제일 중요한것은 백트래킹의 소스구현입니다. 이부분은 설명이 힘드니 소스코드로 확인해주세요.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int map[500][500], check[500][500], n, m;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int dfs(int y, int x, int cnt);
int func(int y, int x);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			check[i][j] = 1;
			//반환받아서 그 값으로 비교하기
			//1. 일반적인 dfs
			ans = max(ans, dfs(i, j, 1));
			//ㅗ,ㅓ,ㅏ,ㅜ의 특별한 형태
			ans = max(ans, func(i, j));
			//백트래킹
			check[i][j] = 0;
		}
	}
	cout << ans << '\n';

}
int dfs(int y, int x, int cnt)
{
	int sum = 0;
	if (cnt == 4)
	{
		return map[y][x];
	}
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 0 && nx >= 0 && ny < n && nx < m && !check[ny][nx])
		{
			check[ny][nx] = 1;
			sum = max(sum, map[y][x] + dfs(ny, nx, cnt + 1));
			check[ny][nx] = 0;
		}
	}
	return sum;
}
int func(int y, int x)
{
	int sum = 0;
	//ㅏ
	if (y - 1 >= 0 && y + 1 < n && x + 1 < m)
		sum = max(sum, map[y][x] + map[y - 1][x] + map[y + 1][x] + map[y][x + 1]);
	//ㅓ
	if (y - 1 >= 0 && y + 1 < n && x + 1 < m)
		sum = max(sum, map[y][x] + map[y - 1][x + 1] + map[y + 1][x + 1] + map[y][x + 1]);
	//ㅗ
	if (y - 1 >= 0 && x - 1 >= 0 && x + 1 < m)
		sum = max(sum, map[y - 1][x] + map[y][x] + map[y][x - 1] + map[y][x + 1]);
	//ㅜ
	if (y + 1 < n && x - 1 >= 0 && x + 1 < m)
		sum = max(sum, map[y][x] + map[y][x - 1] + map[y][x + 1] + map[y + 1][x]);
	return sum;


}

결과

문제 출처: https://www.acmicpc.net/problem/17070

풀이

주어진조건을 이용하여 모든 가능한 경우를 탐색하는 완전탐색 문제입니다.

파이프가 가로방향일 때는 오른쪽과 대각선, 세로방향일 때는 세로방향과 대각선, 대각선 방향일 때는 오른쪽+대각선+세로 모두 이동가능합니다.

이 조건을 이용하여 중요한 부분들을 적어보았습니다.

1. 방향배열(dx,dy)의 요소는 4개가 아니라 3개입니다.(서쪽방향이없음)

2. 파이프끝의 좌표와 현재 방향을 시작으로 dfs연산을 합니다.

3. dfs내부에서 y==n-1&&x==n-1이면 파이프가 끝에 도착한것이므로 경우의수를++해주고 종료합니다.

4. 파이프가 움직일 수 있는 경우에 대해서만 연산 할 수 있게 코드를 작성합니다.

문제에서 주어진 조건 순서대로 파이프가 가로방향일 때, 세로방향일 때, 대각선 방향일 때 움직일 수 있는 경우만 계산합니다.

중요한것은, 대각선 방향일 때, 파이프가 동쪽,남쪽,대각선방향 3칸을 차지하므로, 동쪽,남쪽방향이 벽일 때를 고려해줘야합니다. 

(대각선 방향일 때는 ny,nx로 다음 방향들을 탐색 할 때 if(map[ny][nx]!=1)의 조건에의해 검사됩니다.)

그리고, 구현할 때 굳이 파이프의 방향변수를 선언하여 걍 방향별로 연산을하는 번거로운 코드들을 작성하지않아도됩니다.

왜냐하면 dfs함수 내부에서 한번 연산 할 때 방향별로(동,대각,아래) 한번 씩 수행되기 때문에, 방향별로 탐색하는 for문의 i가 파이프의 방향을 나타내기도 하기 때문입니다. 

만약 pipe변수를 선언하여 0(동쪽)일때, 1(대각선), 2(아래)에 대해 각각 계산하고자 했다면 코드가 길어졌을겁니다. 

코드

#include<iostream>
using namespace std;
int n;
int map[16][16];
//동 대각선,아래
int dx[3] = { 1,1,0 };
int dy[3] = { 0,1,1 };
//파이프방향
int ans;
void dfs(int y, int x, int dir);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	///3번쨰 인자는 파이프방향임(0:동:1:대각2:남)
	dfs(0, 1, 0);
	cout << ans << '\n';
}
void dfs(int y, int x, int dir)
{
	if (y == n - 1 && x == n - 1)
	{
		ans++;
		return;
	}
	//3방향에대해 검색
	for (int i = 0; i < 3; i++)
	{
		//파이프가 가로면 가로+대각선만계산
		if (dir == 0 && i == 2)continue;
		//파이프가 세로면 세로+대각선만계산
		if (dir == 2 && i == 0)continue;
		//대각선일 때
		if (i == 1 && (map[y][x + 1] == 1 || map[y + 1][x] == 1))
			continue;

		int ny = y + dy[i];
		int nx = x + dx[i];
		//범위벗어나지않고 이동한 좌표가벽아닐 때
		if (ny < n && nx < n && map[ny][nx] != 1)
			dfs(ny, nx, i);
	}
}

결과

문제 출처: https://www.acmicpc.net/problem/17144

풀이

어제오늘 합해서 10시간넘게 못풀었던 문제입니다.. 고민했던 시간에 비해 틀린부분이 너무 어렵고 어이없더라구요...삼성..역시 대기업이네요

제가 생각하는 중요한 부분부터 천천히 살펴봅시다.

1.좌표에서 미세먼지가 퍼질 때 ,원본에서 퍼지는 것을 시뮬레이션 하면 안됩니다.

1이상 인 값들이 좌표에 있을 때, 각 값들은 자기자신의 고유의 값을 퍼뜨려야하는데, 원본에서 시뮬레이션을 돌리면 기존의 값들이 수정되어 그 수정된값을 기준으로 퍼뜨리게됩니다. 그게 아니고 원래 자기좌표의 값에서 퍼뜨려야합니다. 즉, 복사본이 필요합니다.

그리고, 주석에도 달아놨는데, 현재자리에서 먼지를 퍼뜨리고 자기자리의 남은 먼지를 계산할때는 원본이아닌 사본을 기준으로 계산해야합니다.

즉, temp[i][j]=map[i][j]-(cnt*val)로 코드작성 시 위의 결과가 나오지않습니다.(예제를 잘 볼 필요가 있습니다.)

2. 맵 복사를 한번하는게 아닙니다.( 문제 잘읽기)

예를들어 t=2일때, t=2일 때 퍼뜨리기+청소연산은 t=1에서 계산한 원본을 사본에 다시 복사해서 계산합니다.(문제만 잘읽으면 됩니다. 제가 실수해서....)

3. 퍼지는 방향을 대충 연산하면 안됩니다. (이거 때문에 10시간.....)

청소기 상단 부, 하단 부에서 회전하며 퍼지는 방향을 그냥 임의의 순서대로 하면안됩니다.

저는 처음에 상단부에서 문제에서 알려준대로 시계방향(오른쪽->위->왼쪽->아래 순), 하단부는 반시계방향(오른쪽->아래->왼쪽->위)로 계산했습니다.

당연하게 생각했고, 여기서 틀린것을 눈치못챘는데, 직접 그려보면, 위처럼 코드작성시, 회전하지않고 좌표밖으로 빠져나가는 숫자들이 생깁니다. 

저처럼 코드를 작성하신분들은 위의 그림(청정기상단부분)에 본인의 식을 직접 대입하며 그려보면 실수임을 할 수 있습니다.

이것을 해결하려면, 공기청정기로 빨려들어가는 부분부터 역순으로 계산하는게 편합니다.

이게 당연한건지는 모르겠는데 이렇게 해야 정확한 연산이 되더라구요. 그리고, 공기청정기 윗부분, 아랫부분의 x좌표+1자리는 따로 0으로 체크해줘야합니다.

즉, 공기청정기에서 불어오는 바람은 따로 0으로 체크해줘야합니다.따로 체크를 해주지않고 방향계산 때 같이 한번에 계산해버리면 공기청정기 자리가 -1이아닌 0으로 바껴버리는 경우가 생깁니다. 

그리고 방향회전 연산 시 잔실수가 나올수 있는 가능성이 높기 때문에 코드를 꼼꼼하게 작성할 필요가 있습니다.

4. 공기청정기의 위치를 pair에 저장할 때 저처럼 이런 잔실수를 하지않기를바랍니다.. (실수한 부분이라 적어둡니다.)

위의 설명들을 총 망라해서 코드로 작성하면 다음과 같습니다.

코드

#include<iostream>
using namespace std;
int map[50][50];
int temp[50][50];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
pair<int, int>p[2];
int r, c, t, ans;
void spread();
void clean_room();
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int index = 0;
	cin >> r >> c >> t;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == -1) {
				p[index].first = i;
				p[index].second = j;
				index++;
			}
		}
	}

	
	//퍼뜨리고 청소하기
	for (int i = 0; i < t; i++)
	{
		spread();
		clean_room();
	}

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (map[i][j] >= 1)
				ans += map[i][j];
		}
	}
	cout << ans << '\n';

}
void spread()
{
	//복사 
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			temp[i][j] = map[i][j];
	
	int cnt, val, ny, nx;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cnt = 0;
			if (map[i][j] != -1 && map[i][j] != 0)
			{
				//temp[i][j]/5하면안됨. 이미 수정되있을수도있는값이므로.
				val = map[i][j] / 5;
				for (int k = 0; k < 4; k++)
				{
					ny = i + dy[k];
					nx = j + dx[k];
					if (ny >= 0 && nx >= 0 && ny < r && nx < c && map[ny][nx] != -1)
					{
						//누적된값을 계속더해감
						temp[ny][nx] = temp[ny][nx] + val;
						cnt++;
					}
				}
				//현재좌표에누적된값에서 빼야되므로 원본map[i][j]에서 빼면안됨!!
				temp[i][j] = temp[i][j] - (cnt * val);
			}
		}
	}
	//원본에 다시 삽입
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			map[i][j] = temp[i][j];
}
void clean_room()
{
	//p[0].first=2,p[0].second=0;
	//청정기 윗부분,아랫부분에 대해
	//주의 : 빨아들여지는 부분부터 역순으로 방향잡아야됨

	for (int i = 0; i < 2; i++)
	{
		//윗부분
		if (i == 0)
		{
			//왼쪽
			for (int i = p[0].first-1; i > 0; i--)
				map[i][0] = map[i-1][0];
			//위쪽
			for (int i = 1; i < c; i++)
				map[0][i - 1] = map[0][i];
			//오른쪽
			for (int i = 1; i <= p[0].first; i++)
				map[i - 1][c - 1] = map[i][c - 1];
			//아래
			for (int i = c - 1; i > 1; i--)
				map[p[0].first][i] = map[p[0].first][i - 1];

				//청소기에서 오는 바람(0) 처리해주기
				map[p[0].first][1] = 0;
				
		}
		//p[1].first=3, p[1].second=0;
		//아래방향
		else if (i == 1)
		{
			//왼쪽
			for (int i = p[1].first + 1; i < r - 1; i++)
				map[i][0] = map[i + 1][0];
			//아래쪽
			for (int i = 1; i < c; i++)
				map[r - 1][i - 1] = map[r - 1][i];
			//오른쪽
			for (int i = r - 1; i >=p[1].first+1; i--)
				map[i][c - 1] = map[i - 1][c - 1];
			//위
			for (int i = c - 1; i > 1; i--)
				map[p[1].first][i] = map[p[1].first][i - 1];
			//청소기에서 오는바람 0처리
			map[p[1].first][1] = 0;
		}
	}
}

결과

문제 출처: https://www.acmicpc.net/problem/3190

풀이

하루에 삼성 기출문제 하나푸는것도 벅차는것같네요.. 하루에 4개 5개씩 푸는분들 진짜...말도안돼 

문제를 제대로 이해하고 풀어보려면 일단 첫번째 test 케이스를 직접 그려보면됩니다.

그려보면 느낄 수 있는 것

1. 방향회전 연산의 시간은 누적되고, X초 전에 벽부딪히거나 자기몸 일부 만나면 종료

ex) 3 'D'  -> 15 'L'   => 3초일때 연산 후 12초 후 15초 일 때 계산

2. 방향 꺾을 때 머리제외한 몸통+꼬리 부분이 벽이 부딪히는걸 어떻게 해결할까?

좌표상에서 방향을 꺾고나서의 뱀의 모양 표현 불가능

-----> 지나갈 때 마다 좌표에 뱀의 흔적을 남기자.

3. 몸의 길이가커지고(사과발견 시) 좌표를 한칸 앞으로 당기는 연산(빈칸 발견시)을 어떻게 처리할까?

꼬리를 삭제하고, 머리를 추가한다(길어진다)? -> 앞 뒤로 삽입삭제 가능한 덱 떠올림

------> 덱에 뱀의 이동경로를 표현하자(요소의 갯수=뱀의 길이가 되게끔)

결론

1. 뱀을 나타내기위해 덱을 사용한다. (머리=front, 꼬리=back)

2. 꼬리를 자를 때(빈칸발견)는 back을 pop시킨다.(꼬리이므로) 

3. 길이가 길어질때는(사과발견) front에 머리좌표를 넣어주자.

4. 뱀이 지나간 좌표를 맵에 표현(2) 하고, 없는 좌표는(꼬리가 짤린 좌표포함) 0으로 표현하자.

5. 뱀이 지나갈 때 값이 2인좌표를 만나면 종료시키자.

코드

#include<iostream>
#include<deque>
#include<vector>
using namespace std;
//꼬리는 0, 머리는 2 


//뱀의위치는 좌표상에2로표시
//뱀의위치가 바뀔떄마다 그 위치를 덱front에삽입
//사실상 덱back의 좌표는 꼬리부분 

//사과 자리 1, 빈자리0
//뱀좌표: 2



//동북서남
int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };
int map[101][101];
vector<pair<int, char>>v;
deque<pair<int, int>>dq;
void func();
int n, time;
int main()
{
	int k, y, x, l,num;
	char c;
	//방향연산의 횟수 
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
	{
		cin >> y >> x;
		map[y][x] = 1;
	}
	cin >> l;
	for (int i = 1; i <= l; i++)
	{
		cin >> num >> c;
		v.push_back(make_pair(num, c));
	}
	
	func();
	cout << time << endl;
}
void func()
{
	//cnt= 연산의 갯수
	int y =1, x = 1, go = 0, cnt=0;
	dq.push_back({ y,x });
	map[y][x] = 2;
	while (1)
	{
		time++;
		int nx = x + dx[go];
		int ny = y + dy[go];
		//벽이나, 자신의 몸의일부만나면 끝
		if (nx<1 || ny<1 || nx>n || ny>n || map[ny][nx] == 2)
			return;

		else if (map[ny][nx] == 0)
		{
			//뱀이 지나감
			map[ny][nx] = 2;
			//꼬리부분이 2로 칠해져있음(지나갔기때문에)
			//0으로 처리해주고 덱에서도 꼬리부분 짜름
			map[dq.back().first][dq.back().second] = 0;
			//덱의 마지막원소(좌표)가 꼬리끝부분(좌표)이므로 짤라버림
			dq.pop_back();
			//머리부분을 front에삽입 : back아님!!
			dq.push_front({ ny,nx });
		}
		else if (map[ny][nx] == 1)
		{
			map[ny][nx] = 2;
			//마찬가지로 front에 삽입 : back아님!!
			dq.push_front({ ny,nx });
		}
		
		if (cnt < v.size()) {
			//연산 횟수에대해 방향갱신
			if (time == v[cnt].first)
			{
				if (v[cnt].second == 'L')go = (go + 1) % 4;
				else if (v[cnt].second == 'D')go = (go + 3) % 4;
				cnt++;
			}
		}
		y = ny;
		x = nx;
	}
}

결과

문제 출처: https://www.acmicpc.net/problem/14503

풀이

최초의 로봇청소기의 좌표로부터 4방향을 검색하면서 방향을 바꾸는 연산이 너무 까다로웠습니다..

로봇 청소기의 좌표 및, 방향을 담을 수 있는 큐를 선언하여 bfs를 이용했습니다. 

현재 자리에서 왼쪽부터 탐색하여 벽이있거나, 이미 청소했을 경우, 방향을 그 쪽으로 돌리는게 핵심이었습니다. 

문제에서 주어진대로 0번 인덱스:북, 1번: 동, 2번 : 남, 3번 서 쪽으로 각각 지정해서 dx[4],dy[4] 좌표를 선언했습니다. 

bfs 수행중에 중요한것은, 네 방향을 방향 순서에 따라 탐색 중, 청소할 수 있는 좌표를 만나면 좌표를 남기고 탈출해야합니다.(4번연산하지않게)

왼쪽부터 탐색하여 향하는 방향을 갱신해주는 연산 코드는 아래와 같습니다. (이게 너무 어려웠습니다.) 매번 향하는 순서가 규칙적이므로, 아래 코드가 성립합니다.

int next_go = (go + (3 - i)) % 4;

그리고 두번 쨰로 까다로운 연산은 후진 할 떄, 방향은 유지하며 후진하는 것입니다. 그런데 사실 까다로운건 없습니다. 아래와 같이 작성하면 이게 곧 그 뜻이됩니다.

int by = y - dy[go];

int bx = x - dx[go];

이렇게 식을 세울줄 알면 끝이라서,, 나머지설명은 주석으로 확인해주세요.

코드

#include<iostream>
#include<queue>
using namespace std;
int map[50][50];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m, r, c, d, room;
queue<pair<pair<int, int>,int>> q;
void bfs();
int main()
{
	cin >> n >> m >> r >> c >> d;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	bfs();
	cout << room;
}
void bfs()
{
	q.push({ {r,c},d });
	while (!q.empty())
	{
		int y = q.front().first.first;
		int x = q.front().first.second;
		int go = q.front().second;
		if (map[y][x] == 0)
		{
			room++;
			map[y][x] = 10;
		}
		q.pop();
		bool check = false;
		for (int i = 0; i < 4; i++)
		{
			//좌표의변화. 이게 너무어려웠음
			int next_go = (go + (3 - i)) % 4;

			int ny = y + dy[next_go];
			int nx = x + dx[next_go];
			//(1,0)인상태)
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				if (map[ny][nx] == 0)
				{
					q.push({ {ny,nx},next_go });
					check = true;
					break;
				}
				
			}
		}

		//네 방향 모두 청소되어있을떄 || 네방향모두 벽일 때
		if (!check)
		{
			//방향을 유지하며 한칸 후진. 
			int by = y - dy[go];
			int bx = x - dx[go];
			//후진할 수 있으면 후진해서 다시 시작
			if ((0 <= by && by < n && 0 <= bx && bx < m) && map[by][bx] != 1)
				q.push({ {by, bx}, go });
			//후진할 수 없으면 종료
			else
				break;
		}
		//빈칸을 찾아서 청소하러 이동한경우 skip
		else
			continue;
	}
}

결과