백준 2931번 가스관

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

2931번: 가스관

 

 

 

 

 

 

<접근방법>

구현, 완전탐색 문제입니다.

 

빈 칸에는 어느 가스관이 들어갈지 모릅니다.

그래서 완전탐색으로 찾아야 합니다.

 

그라고 가스관의 모양에 따라서 이동해야 합니다.

이때 가스관의 모양이 같더라도 입력 방향에 따라서 출력 방향이 달라질 수 있습니다.

그러므로 방향에 대한 정보가 항상 필요합니다.

 

가스관의 입출력은 함수를 만들었습니다.

 

전진 구현은 dfs로 하였습니다.

 

 

 

 

 

 

 

<느낀 점>

문제 접근과 설계 단계가 많이 부족함을 느꼈습니다.

dfs를 잘 다루지 못함을 알았습니다.

케이스 분류를 너무 못합니다. 논리적 사고??

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

struct info {
	int y, x, dir, cnt;
};

struct point {
	int y, x, dir;
};

int n, m, K;
char map[30][30], gas[7] = {'|', '-', '+', '1', '2', '3', '4'};
int dy[4] = {0, -1, 0, 1 };
int dx[4] = {1, 0, -1, 0 };
int ey, ex, ec;
bool visit[30][30], tvisit[30][30];

queue<info> q;

int check(int dir, char c) {
	if (c == '|') {
		if (dir == 1 || dir == 3) return dir;
	}
	else if (c == '-') {
		if (dir == 0 || dir == 2) return dir;
	}
	else if (c == '+') {
		return dir;
	}
	else if (c == '1') {
		if (dir == 1) return 0;
		if (dir == 2) return 3;
	}
	else if (c == '2') {
		if (dir == 2) return 1;
		if (dir == 3) return 0;
	}
	else if (c == '3') {
		if (dir == 0) return 1;
		if (dir == 3) return 2;
	}
	else if (c == '4') {
		if (dir == 0) return 3;
		if (dir == 1) return 2;
	}
	return -1;
}

void dfs(int cnt, bool used, int y, int x, int dir) {
	//기저사례
	if (y < 0 || y >= n || x < 0 || x >= m) return;

	if (map[y][x] == '.') {
		if (used == false) {
			used = true;
			for (int i = 0; i < 7; i++) {
				map[y][x] = gas[i];
				visit[y][x] = true;
				ey = y; ex = x; ec = i;
				dfs(cnt+1, used, y, x, dir);
				map[y][x] = '.';
				visit[y][x] = false;
			}
		}
		return;
	}

	int td = check(dir, map[y][x]);
	if (td == -1) return;

	if (cnt == K) {
		cout << ey + 1 << ' ' << ex + 1 << ' ' << gas[ec] << '\n';
		exit(0);
		return;
	}

	int ty = y + dy[td];
	int tx = x + dx[td];

	if (visit[ty][tx]) {
		dfs(cnt, used, ty, tx, td);
	}
	else {
		visit[ty][tx] = true;
		dfs(cnt + 1, used, ty, tx, td);
		visit[ty][tx] = false;
	}
	
}

int main() {
	int sy, sx, sd;
	int my, mx;

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'M') {
				sy = i; sx = j;
			}
			if (map[i][j] != '.') K++;
		}
	}
	//M, Z 제외 + 빈 칸
	K -= 1;

	for (int i = 0; i < 4; i++) {
		dfs(0, false, sy + dy[i], sx + dx[i], i);
	}

	return 0;
}