/* 17:34 디저트 까페 엔엔 도로가 있습니다. 해당 디저트 까페에서 팔고 있는 디저트의 종류를 의미합니다. 대각선 방향으로 움직일 수 있는 길들이 있습니다. 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 합니다. 사각형 모양을 그리는 것 대각선방향으로 움직이는 것 해당 지역 벗어나기 불가. 같은 종류의 디저트 엑스 -> 디저트의 종류 비지트 배열로 만들기. 하나만 먹는것도 안됨 - > 이동 해야 합니다. 왔던길도 안되지 -> 중복이니. 되도록 많은 디저트를 먹기. 디저트의 수를 정답으로 출력하는 프로그램을 작성하세요. 오께이. 디저트를 먹을 수 없는 경우 -1 을 출력하면 됩니다. 완전탐색입니다. 큐를 사용해서 가도 됩니다. 갈 수 있는 길을 저장해둔다음에, 그것으로 다시 돌아오면 되니까. 출발하는곳과 도는 방향을 다를 수 있지만, 그리는 모양은 5가지 중 하나 입니다. 디저트를 가장 많이 먹을 수 있는 경우는 5인 경우로 디저트의 종류는 6개 입니다. 경우의 수로 나타내기. 돌아와야 한다는 조건이 있어서 이것을 어떻게 해야하는지 궁금합니다. 돌아와야 한다는 조건을 어떻게 사용해야하는지. 방향은 각각 한번만 사용가능합니다. 움직임이 상당히 제한적입니다. 오른쪽 아래로 이동했으면 다음은 반드시 아래왼쪽, 그다음은 위에 왼쪽, 마지막은 위 오른쪽입니다. 그럼 길이에 대한 인덱스만 정해주면 되겠습니다. 도중에 도달하지 못하면, break 를 걸어주면 되겠습니다. 다른 것들은 전진전진 하면 되는데, nx , ny 에 대해서 그 방향에 대해 전진하는 것, 하기 위해서는 while 문을 넣어둡니다. 2번 보기에 대한 것은 넘어가도 됩니다. 왜냐하면 가장 연결이 많이 되는 것만 찾으면 되기 때문입니다. dfs 로풀이해야합니다. 가는 길에 대해서 가는 방향에 대해서 저장을 해야 합니다. 4가지가 도달되고, 원래 왔던 길에 도달 했으면 오께이. 그럼 시작할때 의 값이 아니라 마지막 처리를 어떻게 할 것인지에 대해서 써놓아야는 군요. 오께이. */ #include <iostream> #include <memory.h> #define SIZE 4 #define TEMP 10 // 101 using namespace std; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int dx[] = {1,1,-1,-1}; // 아래오른쪽, 아래왼쪽, 위에왼쪽, 위에 오른쪽 한번씩만사용해야합니다. int dy[] = {1,-1,-1,1}; int ans; int N; int numArr[TEMP]; int x, y, nx, ny; void init() { memset(numArr, 0, sizeof(numArr[0]) * 101); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) map[i][j] = 0; } void problemIn() { cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; } } } void dfs(int i, int j) {
numArr[map[i][j]] = 1; visit[i][j] = 1; x = i; y = j;
for (int i = 0; i < 4; i++) { while (1) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < N && ny < N) { if (visit[nx][ny] == 0 && numArr[map[nx][ny]] == 0) { visit[nx][ny] = 1; x = nx; y = ny; } else { break; } } else { break; } } } if (x == i && y == j) { for (int i = 0; i < 101; i++) { if (numArr[i] == 1) { ans++; } } } } void solve() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dfs(i, j); memset(numArr, 0, sizeof(numArr[0]) * 101); } } } int main(void) { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); solve();
cout << "#" << tc << " " << ans << endl; ans = 0; } } |
풀이 중인데, 길을 계속해서 탐색하고, dfs 입니다. 가져가야하는 변수와 돌아와야 할때, 변수, 그리고 비지트 함수와 갔던 카페에 대해서는 어떻게 처리할지 고민해보도록 하겠습니다. 내일 고 |