[ACM-ICPC][BOJ] 13565 - Percolation 문제풀이

안녕하세요

여행벌입니다.

오늘은 ACM-ICPC 2016 본선 문제인

13565번 Percolation 문제 풀이를 해보겠습니다.

---

[문제해석]

1. M x N 2차원 지도가 입력으로 들어온다.

2. 0이면 지나갈 수 있고, 1이면 지나갈 수 없다.

3. 위에서부터 시작해 맨 아래에 도달할 수 있는지 판별하는 알고리즘을 구현해라.

 

[알고리즘설계]

1. 입력을 String으로 받아서 Int로 한 글자씩 쪼개서 2차원 int형 배열에 저장해준다.

2. 제일 위에 줄에서 0인 값들을 queue에 저장한다.

3. queue를 이용해 BFS 탐색을 진행하고, BFS 탐색이 끝나기 전에 아래에 도달하면 "YES", 아래에 도달하지 못하고 BFS 탐색이 끝나면 "NO"를 출력한다.

 

#include<iostream>
#include<queue>
#include<string>

int map[1000][1000];
bool visited[1000][1000];

using namespace std;

int main(void) {
	int row, column;
	string input;
	queue<int> x;
	queue<int> y;

	cin >> row >> column;
	
	// 입력을 받고, 시작 점들을 셋팅한다.
	for (int i = 0; i < row; i++) {
		cin >> input;
		for (int j = 0; j < column; j++) {
			map[i][j] = int(input[j] - '0');
			if (i == 0 && map[i][j] == 0) {
				x.push(i);
				y.push(j);
				visited[i][j] = true;
			}
		}
	}
	// BFS 탐색을 하자.
	while (!x.empty() && !y.empty()) {
		// 오른쪽으로 갈 수 있는지 Check 하자.
		if (y.front() != (column - 1) && visited[x.front()][y.front() + 1] == false && map[x.front()][y.front() + 1] == 0) {
			x.push(x.front());
			y.push(y.front() + 1);
			visited[x.front()][y.front() + 1] = true;
		}
		// 왼쪽으로 갈 수 있는지 Check 하자.
		if (y.front() != 0 && visited[x.front()][y.front() - 1] == false && map[x.front()][y.front() - 1] == 0) {
			x.push(x.front());
			y.push(y.front() - 1);
			visited[x.front()][y.front() - 1] = true;
		}
		// 위로 갈 수 있는지 Check 하자.
		if (x.front() != 0 && visited[x.front() - 1][y.front()] == false && map[x.front() - 1][y.front()] == 0) {
			x.push(x.front() - 1);
			y.push(y.front());
			visited[x.front() - 1][y.front()] = true;
		}
		// 아래로 갈 수 있는지 Check 하자.
		if (x.front() != (row - 1) && visited[x.front() + 1][y.front()] == false && map[x.front() + 1][y.front()] == 0) {
			if (x.front() == (row - 2)) {
				cout << "YES";
				return 0;
			}
			x.push(x.front() + 1);
			y.push(y.front());
			visited[x.front() + 1][y.front()] = true;
		}
		x.pop();
		y.pop();
	}
	cout << "NO";
	return 0;
}

---

문제가 쉬워서 코딩도 금방 할 수 있었지만, 코드에 반성해야 할 부분이 많은 것 같다...