백준 1194번 (달이 차오른다, 가자., C++, BFS, 비트 마스킹) / 추가 반례 [BAEKJOON]

글쓴이 / / BaekjoonOnlineJudge, C++/CPP

달이 차오른다, 가자.

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초128 MB132535293358637.393%

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다.
하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서,
지레 겁먹고 벙어리가 되어버렸다.
결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다.
이번이 마지막 기회다.
이걸 놓치면 영영 못 간다.
영식이는 민식이가 오늘도 여태 것처럼 그냥 잠들어버려서 못 갈지도 모른다고 생각했다.
하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다.
미로는 다음과 같이 구성 되어져 있다.

  • 빈 칸: 언제나 이동할 수 있다. (‘.’)
  • 벽: 절대 이동할 수 없다. (‘#’)
  • 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’)
  • 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. (‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’)
  • 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. (‘0’)
  • 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (‘1’)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다.
한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50)
둘째 줄부터 N개의 줄에 미로의 모양이 주어진다.
같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다.
그리고, 문에 대응하는 열쇠가 없을 수도 있다.
‘0’은 한 개, ‘1’은 적어도 한 개 있다. 
열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다.
만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

예제 입력 1

1 7
f0.F..1

예제 출력 1

7

예제 입력 2

5 5
....1
#1###
.1.#0
....A
.1.#.

예제 출력 2

-1

예제 입력 3

7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1

예제 출력 3

55

예제 입력 4

3 4
1..0
###.
1...

예제 출력 4

3

예제 입력 5

3 5
..0..
.###.
..1.A

예제 출력 5

6

예제 입력 6

4 5
0....
.#B#A
.#.#.
b#a#1

예제 출력 6

19

예제 입력 7

1 11
c.0.C.C.C.1

예제 출력 7

12

예제 입력 8

3 6
###...
#0A.1a
###...

예제 출력 8

-1

출처

알고리즘 분류

추가 반례 https://www.acmicpc.net/board/view/23445

예제 입력 A

2 7
1F.f#.0
A...#.a

예제 출력 A

-1

예제 입력 B

2 7
1F.f..0
A.....a

예제 출력 B 

6

예제 입력 C

2 7
1F.f#.0
A...#.a

예제 출력 C

-1

예제 입력 D

8 14
1FD...b#....f#
AC.....#.....#
#.....##.....#
#cd....AC....a
1BD....#.....#
AC.....AC.....
#.....#.......
.............0

예제 출력 D

26

예제 입력 E

48 7
1FD....
BC....a
#.....#
#cd....
.BD....
AC.....
#.....#
f#...##
1##.###
##....a
#.....#
#......
..#b#..
...#...
#.....#
.......
#.....#
f#...##
1##.###
##....a
#.....#
#......
..#b#..
...#...
#.....#
.......
.BD....
AC.....
#.....#
f#...##
1##.###
##....a
#.....#
#......
..#b#..
...#...
#.....#
.......
#.....#
f#...##
1##.###
##....a
#.....#
#......
..#b#..
...#...
#.....#
......0

예제 출력 E

67

세로 크기 N과 가로 크기 M (1 ≤ N, M ≤ 50)
소문자 알파벳 열쇠 / 대문자 알파벳 문
1은 적어도 한 개 이상 0은 한 개
탈출이 불가능하다면 -1 출력
BFS로 접근할 생각

입력 확인 코드

#include<iostream>

using namespace std;

constexpr auto MAX = 51;;

int N, M; // 세로 N 가로 M
int startX, startY; // 처음 시작위치를 저장하기 위함 
char map[MAX][MAX];




void Initalization()
{
	cin >> N >> M;

	//전부 이동이 불가능한 벽으로 변경
	for (int i = 0; i <= N+1; i++)
	{
		for (int j = 0; j <= M+1; j++)
		{
			map[i][j] = '#';
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M ; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == '0')
			{
				startY = i;
				startX = j;
			}
		}
	}
}


int main()
{
	Initalization();

	 cout << startX << " " << startY << "  "<< map[0][1];
	 cout << "\n--------------------------------------------\n";
	 
	 for (int i = 0; i <= N + 1; i++)
	 {
	 	for (int j = 0; j <= M + 1; j++)
	 	{
	 		cout << map[i][j];
	 	}
	 	cout << "\n";
	 }

	return 0;
}

중간 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

constexpr auto MAX = 51;;


int N, M; // 세로 N 가로 M
int startX, startY; // 처음 시작위치를 저장하기 위함 
char map[MAX][MAX];

// 하 상 우 좌
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

typedef struct myStruct {
	int x, y;
	bool checkKey[26] = { false };
	int cnt = 0;
	bool checkMap[MAX][MAX] = { false };
};

myStruct tempStruct;

queue<myStruct> myQueue;



void Initalization()
{
	cin >> N >> M;
	myStruct tempStruct;

	//전부 이동이 불가능한 벽으로 변경
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			map[i][j] = '#';
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == '0')
			{
				startY = i;
				startX = j;
				cout << "(startX, startY) : " << startX << " /" << startY << "\n";
			}
		}
	}
}

int BFS()
{

	map[startY][startX] = '.';

	myStruct mystruct;
	mystruct.checkMap[startY][startX] = true;
	mystruct.x = startX;
	mystruct.y = startY;
	myQueue.push(mystruct);
	cout << myQueue.size() << "\n";
	while (!myQueue.empty())
	{
		tempStruct = myQueue.front();
		tempStruct.cnt = myQueue.front().cnt + 1;
		myQueue.pop();
		for (int k = 0; k < 4; k++)
		{
			cout << "\n-----------------움직임 전---------------------\n";

			for (int i = 0; i <= N + 1; i++)
			{
				for (int j = 0; j <= M + 1; j++)
				{
					cout << map[i][j];
				}
				cout << "\n";
			}


			switch (k)
			{
				case 0:
					cout << "\n하\n";
					break;
				case 1:
					cout << "\n상\n";
					break;
				case 2:
					cout << "\n우\n";
					break;
				case 3:
					cout << "\n좌\n";
					break;
			}

			mystruct = tempStruct;
			cout << "mystruct.cnt : "<< mystruct.cnt << "\n";
			cout << "이동전의 위치 : mystruct.x : " << mystruct.x << " mystruct.y : " << mystruct.y << "\n";
			// 상하 좌우로 검색
			mystruct.x = tempStruct.x + dx[k];
			mystruct.y = tempStruct.y + dy[k];
	
			// 맵의 범위를 넘어가거나 // 벽을 만나거나 //  
			if (mystruct.x <= 0 || mystruct.x > M || mystruct.y <= 0 || mystruct.y > N || map[mystruct.y][mystruct.x] == '#' || mystruct.checkMap[mystruct.y][mystruct.x] == true)
			{
				cout << "checkMap[mystruct.y][mystruct.x] : " << mystruct.checkMap[mystruct.y][mystruct.x] << "\n";
				cout << "이동한 후의 위치 : map[mystruct.y][mystruct.x] : " << map[mystruct.y][mystruct.x] << "\n";
				cout << "이동한 후의 위치 :  " << "mystruct.x : " << mystruct.x << " mystruct.y : " << mystruct.y << "\n";
				cout << "맵의 범위를 넘어가거나 // 벽을 만나거나 " << "\n\n";
				continue;
			}
			else if( 65 <= (int)map[mystruct.y][mystruct.x] && (int)map[mystruct.y][mystruct.x] <= 90 )
			{
				cout << "map[mystruct.y][mystruct.x] : " << map[mystruct.y][mystruct.x] << "\n";
				cout << "(int)map[mystruct.y][mystruct.x]] : " << (int)map[mystruct.y][mystruct.x] << "\n";
				cout << "(int)map[mystruct.y][mystruct.x]-65] : " << (int)map[mystruct.y][mystruct.x] - 65 << "\n";
				// 키가 없으면 넘어간다.
				if (mystruct.checkKey[(int)map[mystruct.y][mystruct.x]-65] == false)
				{
					cout << "// 키가 없으면 넘어간다." << "\n\n";
					cout << "이동한 후의 위치 : map[mystruct.y][mystruct.x] : " << map[mystruct.y][mystruct.x] << "\n";
					cout << "이동한 후의 위치 :  " << "mystruct.x : " << mystruct.x << " mystruct.y : " << mystruct.y << "\n";
					continue;
				}
				else
				{
					cout << "// 키가 있으면 빈칸으로 만든다." << "\n\n";
					cout << "이동한 후의 위치 : map[mystruct.y][mystruct.x] : " << map[mystruct.y][mystruct.x] << "\n";
					cout << "이동한 후의 위치 :  " << "mystruct.x : " << mystruct.x << " mystruct.y : " << mystruct.y << "\n";
					map[mystruct.y][mystruct.x] = '.';
					mystruct.checkMap[mystruct.y][mystruct.x] = true;
				}

			}
			else if (97 <= (int)map[mystruct.y][mystruct.x] && (int)map[mystruct.y][mystruct.x] <= 122)
			{
				cout << "/키를 줍고 열쇠 위치를 빈칸으로 만들고 전체 방문 체크 초기화" << "\n\n";
				cout << "이동한 후의 위치 : map[mystruct.y][mystruct.x] : " << map[mystruct.y][mystruct.x] << "\n";
				cout << "이동한 후의 위치 :  " << "mystruct.x : " << mystruct.x << " mystruct.y : " << mystruct.y << "\n";
				mystruct.checkKey[(int)map[mystruct.y][mystruct.x] - 97] = true;
				map[mystruct.y][mystruct.x] = '.';

				for (int i = 1; i <= N; i++)
				{
					for (int j = 1; j <= M; j++)
					{
						cout << "초기화";
						mystruct.checkMap[i][j] = false;
					}
				}

			}
			else if (map[mystruct.y][mystruct.x] == '1')
			{
				// 미로를 탈출합니다.
				return mystruct.cnt;
			}
			else if (map[mystruct.y][mystruct.x] == '.'|| map[mystruct.y][mystruct.x] == '@')
			{
				cout << "빈 공간에 도착" << "\n\n";
				cout << "이동한 후의 위치 : map[mystruct.y][mystruct.x] : " << map[mystruct.y][mystruct.x] << "\n";
				cout << "이동한 후의 위치 :  " << "mystruct.x : " << mystruct.x << " mystruct.y : " << mystruct.y << "\n";
				mystruct.checkMap[mystruct.y][mystruct.x] = true;
				map[mystruct.y][mystruct.x] = '@';
			}
			cout << "\n-----------------움직임 후---------------------\n";

			for (int i = 0; i <= N + 1; i++)
			{
				for (int j = 0; j <= M + 1; j++)
				{
					cout << map[i][j];
				}
				cout << "\n";
			}
			cout << "map[mystruct.y][mystruct.x] : "<< map[mystruct.y][mystruct.x] << "큐에 저장\n";
			myQueue.push(mystruct);
			cout << myQueue.size()<<"\n";
		}
	}

	// 출구를 찾지 못했을 경우 -1 리턴
	return -1;
	
	
	// cout << "A : " << (int)'A' << " a : " << (int)'a' << "\n";
	// cout << "B : " << (int)'B' << " b : " << (int)'b' << "\n";
	//A : 65 Z : 90
	//  a : 97
	//B: 66 b : 98


}

int main()
{
	 cout << ". : " << (int)'.' << " . : " << (int)'.' << "\n";
	// cout << "a : " << (int)'a' << " z : " << (int)'z' << "\n";
	// cout << "B : " << (int)'B' << " b : " << (int)'b' << "\n";
	Initalization();

	cout << "\n--------------------------------------------\n";

	for (int i = 0; i <= N + 1; i++)
	{
		for (int j = 0; j <= M + 1; j++)
		{
			cout << map[i][j];
		}
		cout << "\n";
	}


	cout << "\n\n 답 : " << BFS() << "\n\n\n";

	cout << startX << " " << startY << "  ";
	 cout << "\n--------------------------------------------\n";
	 
	 for (int i = 0; i <= N + 1; i++)
	 {
	 	for (int j = 0; j <= M + 1; j++)
	 	{
	 		cout << map[i][j];
	 	}
	 	cout << "\n";
	 }

	return 0;
}

BFS로 탐색하다
열쇠를 주우면 방문을 초기화
메모리 초과로 고통 받는다.
방문을 체크하는데 및 키를 체크하는데 문제가 있는 듯 하다

메모리 초과 코드 １

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

constexpr auto MAX = 51;


int N, M; // 세로 N 가로 M
int startX, startY; // 처음 시작 위치를 저장하기 위함 
char map[MAX][MAX];
bool checkMap[MAX][MAX][1 << 6] = {false};
// 하 상 우 좌
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

typedef struct myStruct {
	int x, y;
	int checkKey = 0;
	int cnt = 0;
};

myStruct tempStruct;

queue<myStruct> myQueue;



void Initalization()
{
	cin >> N >> M;
	myStruct tempStruct;

	//전부 이동이 불가능한 벽으로 변경
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			map[i][j] = '#';
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == '0')
			{
				startY = i;
				startX = j;
			}
		}
	}
}

int BFS()
{

	map[startY][startX] = '.';
	myStruct mystruct;
	
	mystruct.x = startX;
	mystruct.y = startY;
	myQueue.push(mystruct);
	while (!myQueue.empty())
	{
		tempStruct = myQueue.front();
		tempStruct.cnt = myQueue.front().cnt + 1;
		myQueue.pop();
		for (int k = 0; k < 4; k++)
		{
			mystruct = tempStruct;
			mystruct.x = tempStruct.x + dx[k];
			mystruct.y = tempStruct.y + dy[k];

			if (mystruct.x <= 0 || mystruct.x > M || mystruct.y <= 0 || mystruct.y > N || map[mystruct.y][mystruct.x] == '#')// )|| checkMap[mystruct.y][mystruct.x][mystruct.checkKey] == true)
			{
				continue;
			}
			else if( 65 <= (int)map[mystruct.y][mystruct.x] && (int)map[mystruct.y][mystruct.x] <= 90 )
			{


				if ((mystruct.checkKey & 1 << ((int)map[mystruct.y][mystruct.x] - 64)) <= 0 )
				{
					continue;
				}
				else
				{
					
				}
			}
			else if (97 <= (int)map[mystruct.y][mystruct.x] && (int)map[mystruct.y][mystruct.x] <= 122)
			{

				mystruct.checkKey = mystruct.checkKey | 1 << ((int)map[mystruct.y][mystruct.x] - 96);
			}
			else if (map[mystruct.y][mystruct.x] == '1')
			{
				return mystruct.cnt;
			}
			else if (map[mystruct.y][mystruct.x] == '.')
			{
				
			}
			checkMap[mystruct.y][mystruct.x][mystruct.checkKey] = true;
			myQueue.push(mystruct);
		}
	}

	return -1;
}

int main()
{
	Initalization();
	cout << BFS();
	return 0;
}

메모리 초과 코드 ２

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

constexpr auto MAX = 51;


int N, M; // 세로 N 가로 M
int startX, startY; // 처음 시작 위치를 저장하기 위함 
char map[MAX][MAX];
bool checkMap[MAX][MAX][1 << 6] = { false };
// 하 상 우 좌
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };



typedef struct myStruct {
	int x, y;
	int checkKey = 0;
	int cnt = 0;
};

myStruct tempStruct;
queue<myStruct> myQueue;



void Initalization()
{
	cin >> N >> M;
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			map[i][j] = '#';
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == '0')
			{
				startY = i;
				startX = j;
			}
		}
	}
}

int BFS()
{
	myStruct mystruct;
	map[startY][startX] = '.';
	mystruct.x = startX;
	mystruct.y = startY;
	myQueue.push(mystruct);
	while (!myQueue.empty())
	{
		tempStruct = myQueue.front();
		tempStruct.cnt = myQueue.front().cnt + 1;
		myQueue.pop();
		for (int k = 0; k < 4; k++)
		{
			mystruct = tempStruct;
			mystruct.x = tempStruct.x + dx[k];
			mystruct.y = tempStruct.y + dy[k];

			if (mystruct.x <= 0 || mystruct.x > M || mystruct.y <= 0 || mystruct.y > N || map[mystruct.y][mystruct.x] == '#' || checkMap[mystruct.y][mystruct.x][tempStruct.checkKey] == true)
			{
				continue;
			}
			else if (65 <= (int)map[mystruct.y][mystruct.x] && (int)map[mystruct.y][mystruct.x] <= 90)
			{

				if ((mystruct.checkKey & 1 << ((int)map[mystruct.y][mystruct.x] - 'A')) > 0)
				{
					map[mystruct.y][mystruct.x] = '.';
				}
				else
				{
					checkMap[mystruct.y][mystruct.x][mystruct.checkKey] = true;
					continue;
				}
			}
			else if (97 <= (int)map[mystruct.y][mystruct.x] && (int)map[mystruct.y][mystruct.x] <= 122)
			{
				mystruct.checkKey = mystruct.checkKey | 1 << ((int)map[mystruct.y][mystruct.x] - 'a');
			}
			else if (map[mystruct.y][mystruct.x] == '1')
			{
				return mystruct.cnt;
			}
			else if (map[mystruct.y][mystruct.x] == '.')
			{
				checkMap[mystruct.y][mystruct.x][mystruct.checkKey] = true;
			}
			myQueue.push(mystruct);
		}
	}

	return -1;
}

int main()
{
	Initalization();
	cout << BFS();
	return 0;
}

계속 메모리 초과로 인하여 변경한 내용
-> 키의 유무를 비트 마스킹으로 해결
-> 방문 마킹의 위치 변경

통과된 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
constexpr auto MAX = 51;

int N, M; // 세로 N 가로 M
int startX, startY; // 처음 시작위치를 저장 
char map[MAX][MAX]; // 맵을 저장
bool checkMap[MAX][MAX][1 << 6] = { false }; // 비트 마스킹
// 하 상 우 좌
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

typedef struct myStruct {
	int x, y;
	int checkKey = 0;
	int cnt = 0;
};

myStruct tempStruct;
queue<myStruct> myQueue;



void Initalization()
{
	cin >> N >> M;
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			map[i][j] = '#';
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == '0')
			{
				startY = i;
				startX = j;
			}
		}
	}
}

int BFS()
{
	myStruct mystruct;
	map[startY][startX] = '.';
	mystruct.x = startX;
	mystruct.y = startY;
	myQueue.push(mystruct);
	while (!myQueue.empty())
	{
		tempStruct = myQueue.front();
		tempStruct.cnt = myQueue.front().cnt + 1;
		myQueue.pop();
		for (int k = 0; k < 4; k++)
		{
			mystruct = tempStruct;
			mystruct.x = tempStruct.x + dx[k];
			mystruct.y = tempStruct.y + dy[k];

			// 범위를 벗어나거나 벽이 있을 경우에 넘어간다.
			if (mystruct.x <= 0 || mystruct.x > M || mystruct.y <= 0 || mystruct.y > N || map[mystruct.y][mystruct.x] == '#' 
				|| checkMap[mystruct.y][mystruct.x][tempStruct.checkKey] == true)
			{
				continue;
			}
			else if (65 <= (int)map[mystruct.y][mystruct.x] && (int)map[mystruct.y][mystruct.x] <= 90)
			{ // 문의 위치일 경우

				// 열쇠를 가지고 있다면
				if ((mystruct.checkKey & 1 << ((int)map[mystruct.y][mystruct.x] - 'A')) > 0)
				{
					checkMap[mystruct.y][mystruct.x][mystruct.checkKey] = true;
				}
				else
				{
					//열쇠가 없다면 넘어간다.
					continue;
				}
			}
			else if (97 <= (int)map[mystruct.y][mystruct.x] && (int)map[mystruct.y][mystruct.x] <= 122)
			{
				// 열쇠의 위치일 경우 비트 마스킹
				mystruct.checkKey = mystruct.checkKey | 1 << ((int)map[mystruct.y][mystruct.x] - 'a');
			}
			else if (map[mystruct.y][mystruct.x] == '.')
			{
				// 빈곳일경우 
			}
			else if (map[mystruct.y][mystruct.x] == '1')
			{
				// 도착지점
				return mystruct.cnt;
			}

			checkMap[mystruct.y][mystruct.x][mystruct.checkKey] = true;
			myQueue.push(mystruct);
		}
	}

	return -1;
}

int main()
{
	Initalization();
	cout << BFS();
	return 0;
}

메모리 초과로 고통받은 문제

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

관련 게시물

위로 스크롤