• Home
  • About
    • Dochoi의 소소한 코딩 모음 photo

      Dochoi의 소소한 코딩 모음

      코딩을 하면서 느낀점들을 모은 공간입니다.

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
    • AI
    • Algorithm
    • Algorithm-Test
    • Cloud
    • Docker
    • Kubernetes
    • iOS
    • Culture
  • Projects

[백준] : 19236(청소년 상어)

11 Jul 2020

Reading time ~3 minutes

algorithm-test

19236(청소년 상어)

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <unordered_set>
#include <math.h>
#include <utility>
#include <tuple>

using namespace std;


int dx[] = { 0,-1,-1,-1,0,1,1,1}; // 반시계 방향으로 정의
int dy[] = { -1,-1, 0 ,1,1,1,0,-1 };
int answer = 0;

typedef struct s_fish {
	int d; //direction (0~ 7); 
	int number; // 0 is dead, else is alive , -1 is shark
}t_fish;

typedef struct s_shark {
	int y;
	int x;
	int sum_number;
	int d;
}t_shark;

void move_fish(t_fish map[4][4], int y, int x, vector<tuple<int, int, int > > &tp) //기존 백터 의포인터를 받는다.(참조자 연산)
{
	for (int i = 0; i < 8; i++)
	{
		int d = map[y][x].d + i; // 현재 방향에서 8방향 증가
		if (d >= 8) // 예외처리
			d -= 8;
		int ny = y + dy[d];
		int nx = x + dx[d];
		if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4)
		{
			if (map[ny][nx].number != -1) // 상어가 없으면
			{
				t_fish temp = map[ny][nx];
				map[ny][nx] = map[y][x]; // 스왑
				map[ny][nx].d = d; // 방향 설정
				map[y][x] = temp;
				if (temp.number > 0)
					{
						get<1>(tp[temp.number - 1]) = y;
						get<2>(tp[temp.number - 1]) = x;
					}
					get<1>(tp[map[ny][nx].number - 1]) = ny;
					get<2>(tp[map[ny][nx].number - 1]) = nx;
				return;
			}
		}

	}

}


void next_step(t_fish map[4][4], t_shark shark, vector<tuple<int, int, int > > tp) // 새로운 백터를 받는 복사 생성자가 호출된다
{



	shark.sum_number += map[shark.y][shark.x].number;
	map[shark.y][shark.x].number = -1;
	shark.d = map[shark.y][shark.x].d;

	for (auto elem : tp) //순서가 적은거 부터 움직이자
	{
		int i = get<1>(elem);
		int j = get<2>(elem);
		
		if (get<0>(elem) > 0)
			if (map[i][j].number > 0)//상어자리가 아니고 빈 공간이 아니면
				move_fish(map, i, j, tp);
	}
	// move shark
	int ny = shark.y; 
	int nx = shark.x; 
	int bx = shark.x; // 기존위치 백업
	int by = shark.y;
	for (int i = 0; i < 3; i++) //4x4이기 때문에 최대 3번 움직인다.
	{
		ny += dy[shark.d];
		nx += dx[shark.d];
		if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4)
		{
			if (map[ny][nx].number > 0) // 물고기가 있으면
			{
				t_fish new_map[4][4];
				for(int j = 0 ; j < 4; j++)
					memcpy(new_map[j], map[j], sizeof(map[j])); // 새로운 맵 복사

				new_map[by][bx].number = 0; //자리번호 0으로 초기화
				get<0>(tp[map[ny][nx].number - 1]) = 0; // 죽음 표시
				shark.y = ny;
				shark.x = nx;
				next_step(new_map, shark, tp);
				get<0>(tp[map[ny][nx].number - 1]) = map[ny][nx].number; // 재귀가 끝났으니 다시 살린다.
			}
		}
	}
	answer = max(answer, shark.sum_number);
}

int	main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	vector<tuple<int, int, int > > tp;// 번호 낮은거부터 하기위한 벡터
	t_fish origin_map[4][4];
	for (int i = 0; i < 4;i++)
	{
		for (int j = 0; j < 4; j++)
		{
			t_fish fish;
			cin >> fish.number;
			cin >> fish.d;
			fish.d -= 1; //because of using from 0
			origin_map[i][j] = fish;
			tp.push_back(make_tuple(fish.number, i, j));
		}
	}
	t_shark shark;
	shark.x = 0;
	shark.y = 0;
	shark.d = 0;
	shark.sum_number = 0;

	sort(tp.begin(), tp.end());
	get<0>(tp[origin_map[0][0].number - 1]) = 0; // 죽음 표시
	next_step(origin_map, shark, tp);
	cout << answer;
	return (0);
}

고찰

문제는 길지만 이해하고 나면 간단하다.

구현 과정에 있어서 tuple을 처음 써본지라 시간이 오래걸렸다.

상어가 이동할 때마다 새로운 map배열을 만들어서 재귀 시켜 주었다.

코드를 더 깔끔하게 짤 수 있을 것 같은데 뭔가 더러워졌다. 아쉬움이 남는다.



Algorithm-TestBOJBFSBackTrackingImplement Share Tweet +1