[C++] 백준 2823번: 유턴 싫어

 

 

 

 

문제의 입출력과 힌트를 보면 

막다른 길이 되지않으려면 최소한 현위치에서 동서남북의 방향중 두군데 이상은 뚫여 있어야 한다는 것을 알 수 있다.

 

완전히 나의 힘으로 푼것은 아니고 다른 코딩을 참고하여 문제를 풀었다. 

 

다음은 알고리즘이다.

1. 마을에서 빌딩이면 그냥 지나가고 아니면 동서남북으로 길이 있는지 탐색한다.

2. 동서남북 중 유효한 곳(빌딩이 아니고 마을 밖이 아닌경우)이 길인 경우가 하나 이하이면 막다른 길이다.

      -> 막다른 길임을 표시하는 cycle을 true로 바꾸고 더이상 탐색할 필요가 없으므로 반복문을 나간다.

3. cycle이 true면 1, false면 0을  출력한다.

 

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int R, C;
vector<string> v;

typedef struct {
	int y, x;
}Dir;

Dir moveDir[4] = { {1,0},{-1,0},{0,1},{0,-1} };

int noUturn() {
	bool cycle = false;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (v[i][j] == 'X')
				continue;
			int openPath = 0;
			for (int k = 0; k < 4; k++) {
				int nextY = i + moveDir[k].y;	//다음행
				int nextX = j + moveDir[k].x;	//다음열

				if (0 <= nextY && nextY < R && 0 <= nextX && nextX < C)	
					//다음번째 길이 유효한 자리일때
					if (v[nextY][nextX] == '.')
						openPath++;	
			}

			if (openPath <= 1) {	// 뚫린길이 하나이하 일 경우 (= 막다른 길일 경우)
				cycle = true;
				break;	// 막다른 길을 발견했으니 나머지 볼 필요 없이 반복문을 나감
			}
		}
	}

	return cycle ? 1 : 0;	//막다른 길이 있으면 1 아니면 0을 리턴
}


int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> R >> C;
	
	v.resize(R);

	for (int i = 0; i < R; i++) {
		cin >> v[i];
	}

	cout << noUturn() << endl;

	return 0;
}

 

 

이번 문제를 통해서 struct를 이런식으로 처음 활용해 봤는데 굉장히 신기했고 많이 배울 수 있었다.

 

typedef struct {
	int y, x;
}Dir;

Dir moveDir[4] = { {1,0},{-1,0},{0,1},{0,-1} };

 

이렇게 선언을 하여 동서남북 방향의 길을 정해놓았다. 

이는 for문 안에서의 코드의 복잡도를 향상 시켜 주었다.

 

for (int k = 0; k < 4; k++) {
				int nextY = i + moveDir[k].y;	//다음행
				int nextX = j + moveDir[k].x;	//다음열

				if (0 <= nextY && nextY < R && 0 <= nextX && nextX < C)	
					//다음번째 길이 유효한 자리일때
					if (v[nextY][nextX] == '.')
						openPath++;	
			}

 

동서남북으로 네번의 탐색이 필요하므로 위와같은 for문에서 다음 길의 x와 y를 저런식으로 정의를 해두었다.

 

앞으로 많은 복습이 필요할 듯 보인다.