글 읽기 - 반례 부탁드리겠습니다.

leek018 4년 전 0

0. 동전을 세트 단위로 관리

1. bfs로 접근

2. visit 배열

(1) 동전 개수 만큼 visit배열 생성

(2) 위치, 방향을 고려하여 각자의 visit배열에 방문 체크

(3) 두 동전이 방문한 곳이 이미 방문한 곳이고 방향도 같다면 큐에 넣지 않음.

3. 두 동전중 하나만 보드 범위를 벗어나면 return

제가 놓친게 있을까요 ?

5시간 동안 반례만 주구장창 만들어봤는데 어디서 틀렸는지 찾지 못해서 올립니다..

반례 부탁드립니다 ㅠㅠ

#include <iostream>
#include <string>
#include <queue>
using namespace std;
bool visit[2][4][20][20];
string map[20];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };
int N, M;
struct coinset {
	pair<int, int> coins[2];
};

bool rangeCheck(int x, int y)
{
	if (x < 0 || y < 0 || x >= M || y >= N)
		return false;
	return true;
}

bool visitCheck(int x, int y,int type,int direc)
{
	if (visit[type][direc][y][x])
		return false;
	return true;
}
coinset myCoin;
int bfs()
{
	queue<coinset> q;
	q.push(myCoin);

	int count = 0;
	while (!q.empty())
	{
        //스위치를 누른 횟수
		count++;
        //q size만큼 뽑아서 bfs 돌림.
		int len = q.size();
		for (int i = 0; i < len; i++)
		{			
			coinset ret = q.front();			
			q.pop();
            //4방향으로 탐색
			for (int j = 0; j < 4; j++)
			{	
                //동전 움직이기
				pair<int, int> coin1 = ret.coins[0];
				pair<int, int> coin2 = ret.coins[1];
				int nx1 = coin1.first + dx[j];
				int ny1 = coin1.second + dy[j];
				int nx2 = coin2.first + dx[j];
				int ny2 = coin2.second + dy[j];
                
                //동전을 움직여서 범위를 먼저 체크
				bool rc1 = rangeCheck(nx1, ny1);
				bool rc2 = rangeCheck(nx2, ny2);
                
                // 두 동전중 하나만 map의 범위를 벗어나면 스위치를 누른 횟수 리턴
				if ( rc1 ^ rc2)				
					return count;
                
                // 두 동전 모두 map 범위 내에 있으면
				if (rc1 && rc2)
				{
                    // 움직이고자 하는 위치에 벽이 있으면 현재 자리에 위치 시킴
					if (map[ny1][nx1] == '#') {
						nx1 = coin1.first;
						ny1 = coin1.second;
					}
					if (map[ny2][nx2] == '#')
					{
						nx2 = coin2.first;
						ny2 = coin2.second;
					}
                    // 방문 체크 - 움직이고자 하는 위치에 움직이려는 방향으로 방문한 적 있는지 체크
					bool vc1 = visitCheck(nx1, ny1, 0, j);
					bool vc2 = visitCheck(nx2, ny2, 1, j);
                    // 방향, 위치를 고려해서 방문한적이 있다면 큐에 넣지 않음.
					if (!vc1 && !vc2)
						continue;
					visit[0][j][ny1][nx1] = true;
					visit[1][j][ny2][nx2] = true;
					coinset nCoinset;
					nCoinset.coins[0] = { nx1,ny1 };
					nCoinset.coins[1] = { nx2,ny2 };
					q.push(nCoinset);
				}									
			}
		}
	}
	return -1;
}

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

	cin >> N >> M;
	int coinFound = 0;
	// 동전 입력 받기
	for (int i = 0; i < N; i++) {
		cin >> map[i];
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == 'o')			
				myCoin.coins[coinFound++] = { j,i };
		}
	}
    // bfs 시작
	int ret = bfs();
	cout << ret;
	return 0;		
}

djm03178 4년 전 2

반례입니다.

6 4
####
#o..
#.##
####
#o..
####

leek018 4년 전 0

성은이 망극하옵니다 ㅠㅠㅠ 피골이 상접하고 골수가 마를 때까지 감사인사 씨게 박겠습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드리겠습니다.

leek018 4년 전 0

djm03178 4년 전 2

leek018 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말