코딩무식자 전공생

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

풀이

문제에서 주어진 조건들로 하여금 BFS를 돌리면 됩니다. 해결해야할 조건은 다음과 같습니다.

1. 현위치에서 한칸 왼쪽가기

2. 현위치에서 한칸 오른쪽가기

3. 현위치에서 a칸 왼쪽 가기

4. 현위치에서 a칸 오른쪽가기

5. 현위치에서 b칸 왼쪽 가기

6. 현위치에서 b칸 오른쪽가기

7. 현위치의 a배 왼쪽가기

->현위치의 a배는 무조건 값이 0보다 작게되므로 불가능 

8. 현위치의 a배 오른쪽가기

9. 현위치의 b배 왼쪽가기 

->현위치의 b배는 무조건 값이 0보다 작게되므로 불가능 

10.현위치의 b배 오른쪽가기

총 8가지 조건만 잘 작성하면됩니다.

코드

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

풀이

공주님을 구해라! https://www.acmicpc.net/problem/17836 와 비슷한 문제로, 3차원배열을 이용하여 풀었습니다.

문제가 똑같아보여서 출력하는것만 수정하고(시작점과 도착점도 시간포함) 제출했는데 틀렸습니다. 

공주님 문제는 검을 얻으면 도착할 때 까지 벽(1)을 빈칸(0)으로 간주할 수 있지만, 이 문제는 벽을 안부시거나 딱 한번만 부시기 때문에 

벽을부순 이후와 검을 먹은 이후의 시뮬레이션의 차이가 있으므로 어느정도 수정해야했습니다.

3차원 배열은 벽을 부시지않았을때(0), 벽을 부셨을 때(1)를 표현하기위해 선언하였고 4가지 경우에대해서만 구현하면됩니다.

실제로는 2가지만 구현하면됩니다.

1. 벽을 만났는데 벽을 부순적이없다.

->벽을 뚫었는지를 나타내는 get변수(0:뚫지않았음 1:뚫었음)를 1로 바꿔서 벽을 뚫었다고 표현해주고, 벽을 부순자리의 visited값을 벽 부수기 직전자리의 visited값+1으로 수정시킵니다. 이 때 visited[ny][nx][get]=visited[y][x][get]+1으로 선언하면  현재 벽을 부수지않고 도착한 좌표를 직전자릿값+1으로 바꾼다고도 볼수 있으므로, 

벽을 부수고 도착한 좌표임을 나타내기위해 visited[ny][nx][get+1]=visited[y][x][get]+1로 선언합니다.

2. 빈 칸을 만났는데 방문하지않은곳이다.

직전 좌표값 +1 처리해줍니다. visited[ny][nx][get]=visited[y][x][get]+1 해줍니다. 

1번 처리로 인해 벽을 부순좌표에서 넘어온것과 벽을 부수지않은 좌표에서 넘어온것이 구분됩니다.

3. 벽을 만났는데 벽을 부순적이있다.

-> 어떠한 연산도 하지않고 넘어갑니다. (continue or 분기)

4. 빈 칸을 만났는데 방문한적이 있는곳이다.

-> 어떠한 연산도 하지않고 넘어갑니다. (continue or 분기)

마지막으로 모든 연산 후 큐가 비었음에도 도착좌표에 도착하지않았다면 도착이 불가능함을 의미하므로 -1을 출력합니다.

코드

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

풀이

여러가지 bfs문제를 풀면서 특정 조건이 있을 때 3차원배열을 이용할 수 있음을 배웠습니다.

예를들어 

1. 길을 탐색할 때 벽을 뚫고가거나 벽을 뚫지않고 갈때 도착점에 도달시 최단거리

2. 검을 먹고 도착하거나 검을 먹지않고 도착할 때 최단거리

같은 경우, 기존의 2차원visited배열을 3차원으로 visited[크기][크기][2]로 선언해서 인덱스가 0이고 값이0일 때 벽을 뚫지않고/검을 먹지않고 그 좌표에 도착하지않았음을 의미하고 인덱스가 1이고 값이 1일때 벽을 뚫고/검을 먹고 도착하였다로 해석 할 수 있습니다. 되게 유용한 것 같습니다.

문제에대해 풀이순서대로 작성해보았습니다.

1. visited배열 선언시 3차원으로 선언하여 검을먹고/먹지않고를 표현할 수 있게한다. 

2. y좌표,x좌표, 걸린시간, 검을획득했는지여부를 구조체로 저장하여 큐에담아서 bfs를 돌린다.

3. 검을 만나면 get을 1로 바꿔주고, 도착점에 도착하면 탈출하여 값 출력하기

일반적인 bfs는 다돌려놓고 도착점의 좌표의 visited배열값을 출력하지만 이 문제는 검을 먹고도착/먹지않고 도착 2가지경우가 있으므로 도착했을 때, 큐에 아직 길을 가고있는 좌표들이있던말던 상관없이 도착하기만 하면 그게 곧 최단거리이므로 탈출하여 값 출력한다. 

그렇기 때문에 문제예제처럼 16s가 걸리던 10s가 걸리던 더 짧은 시간을 비교할필요가없음

4. visited배열에 진행시간을 수정해나갈 때 주의하기

일반적인 bfs는 visted[ny][nx]=visited[y][x]+1하여 최단거리를 찾지만, 이 문제는 검을먹고/먹지않고 가는 좌표가 검획득여부에따라 다름

무슨말이냐면, 같은좌표를 가도, 3차원배열이기 때문에 먹지않고 도착하는좌표와 먹고 도착하는좌표의 값은 서로 다름 

따라서 문제예제를보면, 위처럼 코드작성 시 검을 먹은위치는 6이아닌 0이된다. 

검 먹을 때 get이 1이되므로 검을 먹은좌표가 "검을먹은상태에서 검을먹기직전까지온 시간+1로 해석된다.

검의 좌표는 검을 먹지않은 상태에서 검을 먹기직전까지 온 시간 +1이 되어야한다.

따라서 visited[ny][nx][get]=cnt+1로 작성해야한다.

5. 벽 뚫고 가는것 표현하기

굳이 벽을뚫고가는 모션을 표현할 필요없고, 검을 먹은 뒤부터는 모든 좌표를 갈 수 있으므로 다음좌표를 방문했는지만 확인하면된다.

6. 정답 출력시 ans범위 조심하기

ans<=t인지만 확인하면 ans=0일 때 Fail 대신 0이 출력될수 있으므로 , ans>0 or ans>=1의 조건을 붙여준다.

코드

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

두 가지 방법으로 풀어보았습니다. 

첫번 째 풀이는 배열에 담은 요소가 L개가 됐을 때 배열에서 자음과 모음을 매번 확인하는데, 입력범위가 커질 때 비효율적일 것같습니다.

두 번째 풀이는 string을 이용해서 풀었습니다.

풀이1

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

풀이

bfs를 이용하여 풀었습니다. a에서 b로 가는데 연결된 간선의 수가 정답이므로, check[]배열로  방문여부를 확인함과 동시에, 방문된 현재 좌표의 check배열값을 갱신하므로써 정답을 구할 수 있습니다. 주의할것은 14행,15행에서 최대 n=100까지 입력받기 때문에 32행에서 무의식적으로 i=0;i<n으로 조건을 작성하면 틀립니다. 범위 조심하셔야됩니다.

코드

#include<iostream>
#include<queue>
using namespace std;
int map[101][101];
int check[101];
int n, a, b, m, x, y, ans;
void bfs(int pos);
int main()
{
	cin >> n >> a >> b >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		map[x][y] = 1;
		map[y][x] = 1;
	}
	bfs(a);
	if (check[b] == 0)
		cout << -1 << endl;
	else
		cout << check[b] << endl;

}
void bfs(int pos)
{
	queue<int>q;
	q.push(pos);
	while (!q.empty())
	{
		int temp = q.front(); q.pop();
		//조심, i=0;i<n했으면 틀림
		for (int i = 1; i <=n; i++)
		{
			if(map[temp][i]&&check[i]==0)
			{
				check[i] = check[temp] + 1;
				q.push(i);
			}
		}
	}
}

결과

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

풀이

1.육지인 좌표에서 bfs를 돌리고

2. 그 좌표에서 bfs를 돌렸을 때 최단거리를 구함

3. 모든 육지좌표에서 1,2를 수행하며 최단거리 갱신

4. 마지막에 구한 최단거리==정답

핵심: 어떤 육지좌표에서 1,2를 수행하고 다른 육지좌표에서 최단거리를 구할 때 check배열은 0으로 초기화(방문하지않았다고)해야합니다.

그리고 정답을 출력할 때, 최단거리에서 1을 빼준값을 출력해야합니다. 아래 그림을 참조하면됩니다.

당연하지만, bfs가 아래 그림처럼 최단거리로 갱신해주기 때문에  최단거리문제에서 dfs보다 bfs가 훨씬유리합니다.

코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
char map[50][50];
int check[50][50];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n, m;
int cnt;
int max_value = 0;
void bfs(int y, int x);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> map[i];
	
	//육지일때 그 좌표에서 최단거리구해봄
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 'L')
				//육지에서시작되는 각 좌표들로부터의 최단거리를
			{
				bfs(i, j);
				max_value = max(max_value, cnt);
				cnt = 0;
			}
		}
	}
	//육지에서 bfs를돌리면 그 육지의 좌표의 인접한 좌표가2가되므로 하나빼줘야됨
	cout << max_value-1 << '\n';
}
void bfs(int y, int x)
{
	//핵심! 육지인 모든곳을 탐색하므로 한번 탐색할때마다 갱신
	memset(check, 0, sizeof(check));
	queue<pair<int, int>>q;
	q.push({ y,x });
	check[y][x] = 1;
	while (!q.empty())
	{
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			//좌표범위내에서 확인
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				//만약 육지이고, 만나지않았떤길이면
				if (map[ny][nx] == 'L' && check[ny][nx] == 0)
				{
					check[ny][nx] = check[y][x] + 1;
					cnt = max(cnt, check[ny][nx]);
					q.push({ ny,nx });
				}
				
			}
		}
	}
}

결과

문제출처: 

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

풀이

제 코드의 실행시간이 잘 푸신분들에 비해 최대 6배 차이가량납니다. 이해가 어려워서 이 글을 보러오신거면 제 코드를 보고 다른 빠른풀이법을 보시면좋을것같아요.(그분들 코드가 많이 어렵더라구요..) 

제 코드상에서 실행시간을 줄일 수 있을만한 요소에 대해 알고계신분들은 댓글로 지적좀해주세요..

대충 머릿속으로는 구상이되는데 막상 구현할때 벽3개를놓고 연산하는 시뮬레이션과정이 너무어려워서 다른분들의 코드를 조금 참조했습니다...

백트래킹 기법도 쓰이는데, 제 생각에 dfs,bfs문제중에 어려운문제는 거의 백트래킹+브루트포스+dfs or bfs 같네요.. 어렵습니다.

글로써봤자 이해가 안가니 주석과 코드를 보고 흐름을 따라가보시면 이해가편할 것 같습니다.

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
//벽을 세움
//벽3개를세움
//벽3개를 세울 때 bfs,
//그 bfs를돌렷을때 각 최댓값비교
int map[8][8];
int temp[8][8];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int n, m, area;
void make_wall(int wall);
void bfs();
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];

	//비어있는공간있을떄 그떄 temp로복사받음
	//비어있는 공간,그 자리에서부터 벽3개를 놓는 시늉을 다 돌림
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 0)
			{
				for (int i = 0; i < n; i++)
					for (int j = 0; j < m; j++)
						temp[i][j] = map[i][j];

				//현재 자리에 벽세움
				temp[i][j] = 1;
				make_wall(1);
				//다시원상복구
				temp[i][j] = 0;
			}
			
		}
	}
	cout << area << '\n';
}
void make_wall(int wall)
{
	//벽3개 만들었으면 bfs돌림
	if (wall == 3)
	{
		bfs();
		return;
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//좌표가 0이면
			if (temp[i][j] == 0)
			{
				//벽을 세우고
				temp[i][j] = 1;
				//벽을 한칸늘렸으니 3개인지확인
				make_wall(wall + 1);
				//위의함수로 그자리에서 모든연산끝났으니 다시 0으로,
				temp[i][j] = 0;
			}
		}
	}
}
void bfs()
{
	//temp변수로 갖고놀면 virus가 퍼질떄 temp가 수정되므로 다시 배열복사
	int virus[8][8];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			virus[i][j] = temp[i][j];

	queue<pair<int, int>>q;
	//바이러스좌표를 저장하여 퍼뜨림
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (virus[i][j] == 2)
				q.push({ i,j });

	//퍼뜨려서,
	//최종적으로 map에서 0인 현재좌표에서
	//벽3개를 가정하고, 퍼뜨렸을 때 최대안전영역구함
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				if (virus[ny][nx] == 0 )
				{
					virus[ny][nx] = 2;
					q.push({ ny,nx });
				}
			}
		}
	}
	//최대영역구하기
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (virus[i][j] == 0)
				cnt++;
		}
	}
	area = max(area, cnt);
}

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

풀이

연결요소의 갯수와 bfs / dfs를 했을 때 그 연결요소의 거리를 구하면 되는 탐색문제입니다.

n=25일때 단지의 갯수는 최대 25*25개이므로, 단지의 갯수를 담을수있는 1차원배열과, 단지의 갯수,번호의 갯수를 나타낼수 있게 cnt, index변수만 선언하여 연산하면됩니다. 주석에 상세히 설명을 해놨으니 참고해주세요.

코드

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
char map[25][25];
int check[25][25];
//단지는 1차원배열로선언,최악의경우 n=5일때 모든칸이 1로채워질때
int danji[25 * 25 + 1];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n;
int cnt;
int index;
void bfs(int y, int x);

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> map[i];

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//길이있고, 방문하지않은 노드면?
			if (map[i][j] == '1' && check[i][j] == 0)
			{
				//그 자리서부터 연산돌림
				bfs(i, j);
				//단지의 갯수, 그 단지의마을갯수를 구하기위한 선언
				danji[index++] = cnt;
				cnt = 0;
			}
		}
	}
	//단지의 마을갯수가적은순으로정렬
	sort(danji, danji+index);
	//단지갯수
	cout << index <<  endl;

	for (int i = 0; i < index; i++)
		cout << danji[i] << endl;
}
void bfs(int y, int x)
{
	queue<pair<int, int>>q;
	q.push({ y,x });
	//까먹지말자 check 
	check[y][x] = 1;
	//일단 bfs조건을 맞추고왔으므로 카운팅
	cnt++;
	while (!q.empty())
	{
		y = q.front().first;
		x = q.front().second;
		//까먹지말자pop
		q.pop();
		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 < n) {
				if (map[ny][nx] == '1' && check[ny][nx] == 0)
				{
					q.push({ ny,nx });
					check[ny][nx] = 1;
					//카운팅
					cnt++;
				}
			}
		}
	}
}

결과