[백준] 1730: 판화

문제 링크

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

접근 방식 / 풀이

아이디어를 떠올리고 예외 처리를 하는 데 상당히 까다로웠던 문제라고 생각한다. 반례를 잘 떠올려보는 연습을 해야할 듯 싶다 :(

한 번 움직일 때, 두 점을 연결하고, 그것이 어떤 모양새를 띄는 지를 생각해보아야 한다.

#아래로 움직이는 경우 ('D')
. . . .		| . . .
. . . .		| . . .
. . . .		. . . .
. . . .		. . . .

위와 같이 한 번의 움직임에 두 곳이 바뀐다는 점을 알아야 한다!
이 다음에, 우측으로 움직인다고 해보자.

#아래, 오른쪽으로 움직이는 경우 ('DR')
. . . .		| . . .
. . . .		+ - . .
. . . .		. . . .
. . . .		. . . .

현재 위치를 +로 바꿔준 다음에, 이동한 위치를 -로 바꿔준다.

하지만 이동하려는 위치가 막혀있다면 어떻게 해야 할까?

#아래, 왼쪽으로 움직이는 경우 ('DL')
. . . .		| . . .
. . . .		| . . .
. . . .		. . . .
. . . .		. . . .

아무런 변화가 없다.
따라서, 이전 방향과 수직이 되는 방향이 입력으로 주어질 때, "현재 위치를 +로 바꾼 다음, 이동할 위치를 구하고 그것이 존재하지 않는다면 아무것도 하지 않는다" 라는 생각은 매우 위험하다.

이런 경우를 따져보면서, 결론적으로 구현하게 된 흐름은 다음과 같다.

1. 현재 위치를 저장한다.

2. 다음 위치를 구한다. (이동이 불가능하다면 set_dir의 리턴값은 0이고, continue 를 하여 다음 입력을 받는다.)

3. 이전 방향과 현재 방향을 구분하여 진행한다.

• 이전 방향이 현재 방향과 같다면 x_tmp와 y_tmp, 그리고 현재 위치인 x, y도 현재 방향에 맞춰 설정한다.
• 이전 방향이 현재 방향과 수직이면, x_tmp와 y_tmp는 +가 되어야 하고, 이동한 방향은 현재 방향(U, D : '|' R, L : '-') 에 맞춰 설정한다.
• 이때, 수정하려는 위치에 +이 존재한다면, 수정하지 않는다.

---

답안 코드 링크 (Github)

Github Solution Link

정답 코드 (C++)

#include <iostream>
#include <string>
#include <utility>
#include <memory.h>

using namespace std;

char	map[11][11];
char	pre;
int		n, x, y, x_tmp, y_tmp;
void	fastio(void);
int		set_dir(char c);
void	set_map(char prev1, char prev2, char c1, char c2);

int main(void)
{
	string	s;

	fastio();
	cin >> n;
	cin >> s;
	memset(map, '.', sizeof(map));
	for (int i = 0; i < n; i++)
		map[i][n] = 0;
	for (int i = 0; i < s.length();i++)
	{
		x_tmp = x;
		y_tmp = y;
		if (!set_dir(s[i]))
			continue;
		switch (s[i])
		{
			case 'D':
			case 'U':
				set_map('D', 'U', '|', '-');
				break;
			case 'R':
			case 'L':
				set_map('R', 'L', '-', '|');
				break;
		}
		pre = s[i];
	}
	for (int i = 0; i < n; i++)
		cout << map[i] << "\n";
	return (0);
}

void	set_map(char prev1, char prev2, char c1, char c2)
{
	if (pre == 0 || pre == prev1 || pre == prev2)
	{
		if (map[x_tmp][y_tmp] != '+')
		{
			if (map[x_tmp][y_tmp] == c2)
				map[x_tmp][y_tmp] = '+';
			else
				map[x_tmp][y_tmp] = c1;
		}
		if (map[x][y] != '+')
		{
			if (map[x][y] == c2)
				map[x][y] = '+';
			else
				map[x][y] = c1;
		}
	}
	else
	{
		map[x_tmp][y_tmp] = '+';
		if (map[x][y] != '+')
		{
			if (map[x][y] == c2)
				map[x][y] = '+';
			else
				map[x][y] = c1;
		}
	}
}

int	set_dir(char c)
{
	pair<int, int>	dir[4] = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
	int tmp;
	switch (c)
	{
		case 'D':
			tmp = 0;	break;
		case 'U':
			tmp = 1;	break;
		case 'R':
			tmp = 2;	break;
		case 'L':
			tmp = 3;	break;
	}
	if (x + dir[tmp].first >= 0 && x + dir[tmp].first < n && y + dir[tmp].second >= 0 && y + dir[tmp].second < n)
	{
		x += dir[tmp].first;
		y += dir[tmp].second;
		return (1);
	}
	return (0);
}

void	fastio(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}