[백준] 16197번 두 동전

반응형
반응형

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

  • 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
  • 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
  • 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

  • o: 동전
  • .: 빈 칸
  • #: 벽

동전의 개수는 항상 2개이다.

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

 

#include <bits/stdc++.h>
using namespace std;
int N,M;

string maps[30];

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};


int shift(int step, int x1, int y1 , int x2, int y2) {
  if (step == 11) return -1;

  bool fall1 = false;
  bool fall2 = false;
  if (x1 < 0 || N  <= x1  || y1 < 0 || M <= y1) {
    fall1 = true;
  }

  if (x2 < 0 || N  <= x2  || y2 < 0 || M <= y2) {
    fall2 = true;
  }

  if (fall1 && fall2) return -1;

  if (fall1 || fall2) return step;

  int ans = -1;
  for(int i = 0;i<4;i++) {
    int nx1 = x1 + dx[i];
    int ny1 = y1 + dy[i];

    int nx2 = x2 + dx[i];
    int ny2 = y2 + dy[i];

    if (0<= nx1 && nx1 < N && 0 <= ny1 && ny1 <M && maps[nx1][ny1] == '#') {
      nx1 = x1;
      ny1 = y1;
    }

    if (0<= nx2 && nx2 < N && 0 <= ny2 && ny2 <M && maps[nx2][ny2] == '#') {
      nx2 = x2;
      ny2 = y2;
    }

    int temp = shift(step+1,nx1,ny1,nx2,ny2);

    if (temp == -1) continue;
    if (ans == -1 || ans > temp) {
      ans = temp;
    }
  }

  return ans;


}
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
 
  cin >> N  >> M;

  int x1,y1,x2,y2;
  x1 = x2 = y1 = y2 = -1;

  for(int i = 0; i<N;i++) {
    cin >> maps[i];
    for(int j = 0; j< M;j++) {
      if (maps[i][j] == 'o') {
        if (x1 == -1) {
          x1 = i;
          y1 = j;
        } else {
          x2 = i;
          y2 = j;
        }
        maps[i][j] = '.';
      }
    }
  }

  cout << shift(0,x1,y1,x2,y2) << "\n";

} 

이 문제는 dfs로 푸는 문제다. 이유는 잘 모르겠지만... 그러는 편이 편할 것 같다.ㅎㅎ

아무튼 이 문제에서 다른 2개의 값을 동시에 구하는 방법을 배웠다. 바로 -1로 초기화시켜놓는 행위다. 물론 -1,-1이 있긴하겠지만... 여기서는 0,0부터 시작되기 때문에 아마 -1로 두면 여기서는 가능하지 않는 방법이라 이렇게 하였다.

 

그리고 maps[i][j]를 하는 이유는 이것을 안하게 되면 똑같은 일을 또 하기 때문에 x1과 x2의 값이 같아 질지도 모른다.

 

이제 shift 메소드를 활용해서 동전을 옮겨볼 예정이다. 일단, 시작점과 x,y를 차례대로 넣어준다.

동전이 n개라면... ㄷㄷ 아마 배열에 저장해야하지 않을까?

 

조건에 10번 넘게 입력하면 안된다고 했으니 그 최솟값인 11을 입력하는 순간 -1을 반환하도록 한다. 이것을 안 해주면 무한 반복되 결국 프로그램이 종료될지도 모른다.

 

그리고 동전이 하나만 떨어져야 한다. 그렇게 하기 위해서는 bool 변수를 활용해서 두개 다 떨어지면 -1을 반환하도록 했다. 왜 || 일때 step을 리턴 시키는 이유는 두 개다 같은 경우는 위에서 리턴 시켰기 때문에 그 값들은 들어오지 않는다는 확신이 있기 때문이다.

ans는 추후에 설명하고...

 

방향 벡터를 활용해서 x좌표와 y좌표를 움직여 준다.

근데 여기서 주의 할점이 있다. continue로 제어하게 되면 동전 2개를 따로 조작하는게 아니라 동시에 조작하는 꼴이 되버린다. 왜냐하면 continue하는 순간 다음 값으로 넘어가기 때문이다. 이를 방지하기 위해 전 값을 주입시켜줬다.

그래야 벽을 만나면 원래값으로 돌아올 수 있기 때문이다.

 

근데 여기서도 범위 설정을 해주는 이유는 아마도 가상의 벽이 있을지도 모른다는 그런 이유가 아닐까? 

 

만약 temp가 -1이라면 현재는 불가능하기 때문에 다시 좌표를 바꿔준다.

그리고 최솟값을 구해주면 되는데 여기서도 ans가 -1인 이유는 값을 바꿔주기 위함인데... 왜 -1이냐는 잘 모르겠다. 아마도 이것 또한 동전이 하나만 존재할 경우도 생각해서 절대로 불가능한 값을 설정해웠다.

 

그리고 자연스럽게 ans를 리턴 시켜주면 된다. 

 

위에서 이문제를 dfs라 불렀는데, 브루트 포스일수도 있고, 백트래킹일 수도 있을 것 같다.

 

#include <bits/stdc++.h>
using namespace std;

bool v[25][25][25][25];
char s[25][25];

int dy[]{ 0,0,1,-1 };
int dx[]{ 1,-1,0,0 };

int n, m;

bool f(int y, int x)
{
	return y > 0 && x > 0 && y <= n && x <= m;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int i, j;
	cin >> n >> m;
	int y1 = -1, x1, y2, x2;
	for (i = 1; i <= n; i++)
	{
		cin >> s[i] + 1;
		for (j = 1; j <= m; j++)
			if (s[i][j] == 'o')
				(y1 == -1) ? (y1 = i, x1 = j) : (y2 = i, x2 = j);
	}
	v[y1][x1][y2][x2] = true;
	queue<pair<int, int>> q1, q2;
	q1.push({ y1, x1 });
	q2.push({ y2, x2 });
	int t = 1;
	while (q1.size() && t <= 10)
	{
		for (j = q1.size(); j; j--)
		{
			auto x = q1.front(); q1.pop();
			y1 = x.first; x1 = x.second;
			auto y = q2.front(); q2.pop();
			y2 = y.first; x2 = y.second;

			for (i = 0; i < 4; i++)
			{
				int ny1 = y1 + dy[i];
				int nx1 = x1 + dx[i];
				int ny2 = y2 + dy[i];
				int nx2 = x2 + dx[i];
				if (!f(ny1, nx1) && !f(ny2, nx2))
					continue;
				if (!f(ny1, nx1) || !f(ny2, nx2))
					return cout << t, 0;
				if (s[ny1][nx1] == '#')
					ny1 = y1, nx1 = x1;
				if (s[ny2][nx2] == '#')
					ny2 = y2, nx2 = x2;
				if (!v[ny1][nx1][ny2][nx2])
				{
					v[ny1][nx1][ny2][nx2] = true;
					q1.push({ ny1, nx1 });
					q2.push({ ny2, nx2 });
				}
			}
		}
		t++;
	}
	cout << -1;
}

 

bfs풀이.

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 10987번 모음의 개수  (0) 2020.05.22
[백준] 6679번 싱기한 네자리 숫자  (0) 2020.05.19
[백준] 16922번 로마 숫자 만들기  (0) 2020.05.16
[백준] 14226번 이모티콘  (0) 2020.05.15
[백준] 14502번 연구소  (0) 2020.05.15

댓글

Designed by JB FACTORY