[C++] 순서대로 방문하기

[문제]

Softeer

Softeer

[문제 풀이]

백트래킹을 이용해서 순서대로 방문하는것을 확인하는 문제이다.

처음 고민했던 부분은 bfs에서는 방문한 순간 모두 방문처리를 하는데 해당 문제에서 방문처리를 어떻게 하냐가 고민이었다.

그래서 앞서 말한 백트래킹을 이용해서 visited 처리를 할 수 있었다.

 

void backTrack(int x, int y, int idx){
	if(idx == m){
		answer++;
		return;
	}

	for(int i = 0;i<4;i++){
        if(범위 안이고){
            if(벽이 아니라면){
                if(방문을 아직 하지 않았다면){
                	방문처리후
                    재귀를 이용해 백트래킹 돌려주기.
                    backTrack()
                    방문처리 다시 풀기.
				}
			}
		}
	}

	return;
}

 

밑의 코드에서는 괜히 변수도 많고 추가 조건도 있어서 보기 어려울 수 있어서 위와 같이 설명을 추가한다.

기존에 백트래킹에서 보통 많이 보였던 것처럼 재귀를 써서 조건이 충족되면 return을 해주고 for문을 이용해서 4방향을 돌면서 3가지 조건에 충족이 되는지 확인 후 방문확인 -> 백트래킹 -> 방문확인 풀기 순서가 되게 함수를 만들었다.

 

이제 여기에 추가로 idx 변수와 seq 벡터를 이용해서 순서대로 방문을 하는지를 확인만 해주면 된다.

오랜만에 백트래킹을 응용한 문제라 헷갈릴수 있지만 천천히 해보면 어렵지 않다는 것을 알 수 있다.

[회고]

시험때도 풀었는데 충분히 시간 안에 풀만한 문제였다. 어렵진 않았었음.

[코드]

#include<iostream>
#include <vector>

using namespace std;

int n,m;
int answer;
int graph[5][5];
int visited[5][5];
vector<pair<int, int> > seq(20);

void backTrack(int x, int y, int idx){
	if(idx == m){
		answer++;
		return;
	}

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

	for(int i = 0;i<4;i++){
		int nextX = x + dx[i];
		int nextY = y + dy[i];
		//범위 안이고
		if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < n){
			//벽이 아니고
			if(graph[nextX][nextY] == 0){
				//방문을 하지 않았다면
				if(visited[nextX][nextY] == 0){
					visited[nextX][nextY] = 1;
					//idx 순서라면
					if(nextX == seq[idx].first - 1 && nextY == seq[idx].second - 1){
						backTrack(nextX,nextY, idx + 1);
					}
					else {
						backTrack(nextX,nextY, idx);
					}
					visited[nextX][nextY] = 0;
				}
			}
		}
	}

	return;
}

int main(int argc, char** argv)
{
	cin>>n>>m;
	for(int i = 0;i<n;i++){
		for(int j = 0; j<n;j++){
			cin>>graph[i][j];
		}
	}

	for(int i = 0;i<m;i++){
		cin>>seq[i].first>>seq[i].second;
	}
	visited[seq[0].first - 1][seq[0].second - 1] = 1;

	backTrack(seq[0].first - 1, seq[0].second - 1, 1);
	cout<<answer<<endl;

	return 0;
}