반응형

 

 

 

석유 시추 bfs 로  석유를 미리 번호를 지어두는 작업이 필요하다고 생각한다.

그리고 좌측부터 1자로 내리면서  제일큰걸 확인해보면 되는문제라 생각한다.

 

 

 

해당문제라면

 

1 [ 0,0], [ 0,1] [ 0,2] [ 0,3] [ 0,4]....  12

2 [2,0] [ 2,1] [ 2,2] 3

....

 

재귀로 bfs 탐색을하며 해당처럼 데이터를 모아준다

 

모아두었기때문에 한번 건들인 석유를 두번 캐지않을수있다.

 

 

 

#include <string>
#include <vector>
#include <unordered_map>
#include<queue>
using namespace std;


static int const nextland[4][2]{ {0,1}, {1,0}, {-1,0}, {0,-1} };

//석유 룰 묶어주는 함수
void find_oil(vector<vector<int>>& land, int x, int y, int& oil_count, unordered_map<int, int>& oil_monny) {
	queue<tuple<int, int>> nextxy;
	nextxy.push(make_tuple(x, y));
	land[x][y] = oil_count;
	oil_monny[oil_count]++;
	while (nextxy.size() != 0)
	{


		tuple<int, int> nxy = nextxy.front();
		int xy[2]{ get<0>(nxy),get<1>(nxy) };
		nextxy.pop();


		int x, y = 0;
		for (auto arrow : nextland) {
			y = arrow[1] + xy[1];
			x = arrow[0] + xy[0];
			if (x >= 0 && x < land.size() && y >= 0 && y < land[0].size() && land[x][y] == 1) {
				land[x][y] = oil_count;
				oil_monny[oil_count]++;
				nextxy.push(make_tuple(x, y));
			}
		}
	}
	oil_count++;
}

int solution(vector<vector<int>> land) {
	int answer = 0;
	int oil_count = 2;
	unordered_map<int, int> oil_monny;

	for (int i = 0; i < land.size(); i++) {
		for (int j = 0; j < land[i].size(); j++) {
			if (land[i][j] == 1) {
            
            //석유를 한번에 모아주고 그 모은 석유의 벨류 탐색
				find_oil(land, i, j, oil_count, oil_monny);
			}
		}
	}


	for (int i = 0; i < land[0].size(); i++) {
		vector<bool>c(oil_count - 2);
		int b =0;
		for (int j = 0; j < land.size(); j++) {
        //아래로 내리면서 기름 있는땅 찾고 만약 탐색 안되었으면
			if (land[j][i] > 1 && (c[land[j][i] - 2] == false)) {
            //탐색완료 표시
				c[land[j][i] - 2] = true;
				// 현재 벨류 추가
                b += oil_monny[land[j][i]];
			}
		}
		if (answer < b) {
			answer = b;
		}
	}

	return answer;
}

 

반응형

 

https://school.programmers.co.kr/learn/courses/30/lessons/258711

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

문제가 길다

 

간단 하게 설명하자면

 

그래프들은 1개이상의 정점과 정점들을 연결하는 단방향 간선 으로 이루어져 있다.

 

위 처럼 도넛 모양 그래프 막대모양 그래프 8자모양 그래프가 여러가지 있다.

 

그래프들과 무관한 정점을 하나 생성한뒤 그래프들을  임의의정점 하나로 향하는 간선들을 연결하였다.

 

그후 각 정점에 서로 다른 번호를 매겼다.

 

생성한 정점의 번호와 정점을 생성하기전 그래프들의 수를 구해야 한다.

 

return [생성한 정점의 번호, 도넛모양 그래프수,막대모양 그래푸수,8자모양그래프수]

 

 

해당 문제의 입출력 예제를 보자면

 

1번 = 도넛모양

 

4->3 = 막대모양 그래프

2 = 임의의 정점 

 

그럼으로 return [2,1,1,0]

 

 

정점들을 탐색하며 노느들이 해당하는 정보를 알면되는 간단한 문제다.

 

 

간선은 단방향 단선뿐이며,  

 

노느들의 특징은

 

도넛모양은 시작위치에서 모든 노드들을 한번씩 거친후 다시 첫 노드로 돌아온다는것이다.

 

단방향노드는 마지막노드까지 탐색후 끝난다.

 

8자모양 그래프는 시작노드로 오기전 중간노드를 거친후 돌아온다

 

도넛모양과 유사하지만 같은노드를 다시 만났을때 처음 시작한 노드가 아니라는 점이 다르다.

 

해당문제는 시작 노드와 간선들의 특징만 생각하면 어렵지않다.

 

 

map 에 정점과 간선들을 추가해주면서

특징들을 확인하기위해 

 

간선이 나가는 횟수와

 

자신을 가리키는 간선이 있는지 확인한다 


	unordered_map<int, vector<int>> map;
for (auto e : edges) {
		map[e[0]].push_back(e[1]);
		edin[e[0]]++;
		Bedin[e[1]] = true;
	}

 

 

 

 간선이 나가는 수를 저장했던 edin을 반복하면 노드들을 전부 탐색한다

 

제일크며 Bedin로 나에게 도착했던간선이 없는 노드를 찾으면

시작부분일것이다

 

단방향 간선이 존재하기에 간선수를 추가로 확인했다.

	int s = 0;
	for (auto i : edin) {
		if (s < i.second && !Bedin[i.first])
		{
			s = i.second;
			start_N = i.first;
		}
	}
	answer[0] = start_N;

 

시작 노드에서 나가는 그래프들을 전부 돌면서 무슨 그래프인지만 알아내면 된다.

	for (auto num : map[start_N]) {
		star = num;
		answer[Solution_find(map, num)]++;
	}

 

만약  현재노드의간선이 없다면? 직선 2번

다시도착한게 size가 1이상이면 8번

다음 간선이 start 까지 도착했다면 도넛모양

다음노드 탐색

 

int Solution_find(unordered_map<int, vector<int>>& m, int num) {
	if (m[num].size() > 1)return 3;
	if ((m[num].size() == 0)) return 2;
	if (m[num][0] == star) return 1;
	for (int i = 0; i < m[num].size(); i++)
		return Solution_find(m, m[num][i]);
}

 

 

 

 

#include<queue>
#include <unordered_map>
#include<vector>
#include<iostream>

using namespace std;
int star = 0;
int Solution_find(unordered_map<int, vector<int>>& m, int num) {
	if (m[num].size() > 1)return 3;
	if ((m[num].size() == 0)) return 2;
	if (m[num][0] == star) return 1;
	for (int i = 0; i < m[num].size(); i++)
		return Solution_find(m, m[num][i]);
}

vector<int> solution(vector<vector<int>> edges) {

	vector<int> answer(4);

	unordered_map<int,int> edin;
	unordered_map<int,bool> Bedin;
	int start_N = 0;
	unordered_map<int, vector<int>> map;
	for (auto e : edges) {
		map[e[0]].push_back(e[1]);
		edin[e[0]]++;
		Bedin[e[1]] = true;
	}
	int s = 0;
	for (auto i : edin) {
		if (s < i.second && !Bedin[i.first])
		{
			s = i.second;
			start_N = i.first;
		}
	}
	answer[0] = start_N;

	for (auto num : map[start_N]) {
		star = num;
		answer[Solution_find(map, num)]++;
	}


	return answer;
}

 

반응형

 

https://school.programmers.co.kr/learn/courses/30/lessons/43164

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 


BFS와 DFS 문제 레벨3 단계의 여행경로 문제다.

이해하는 데 확실히 오래 걸린 문제다



처음 생각은 그냥 DFS 문제인 줄 알고 알파벳 정렬 후 빠른 순으로 탐색하였다.
풀면 채점 시 1번 2번 실패, 3번 4번 성공한다.



생각해 낸 아이디어는
위 문구처럼 무조건 다 갈 수 있다는 이야기는


만약 끝까지 탐색 DFS를 했을 경우에도 모든 티켓(간선)을 사용하지 않았다면 그 간선은 마지막에 방문해야 하는 간선이다.


또한 같은 티켓이 두 개일 수 있다.





1. 그래프를 만들며 그래프를 알파벳순으로 정렬한다.
2. 그래프를 순서대로 탐색한다.
3. 더 이상 다른 노드로 이동할 수 없는 경우 사용한 티켓(간선)의 개수와 전체 티켓(간선)의 개수를 체크한다.
3.1달을 경우 이전 노드로 돌아간다.
4 만약 돌아왔으면 다음 2로 돌아가 다음 순서 노드를 탐색한다.

#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int ticketSize = 0;
vector<string>Aanswer;
bool findAir(string start,int num,vector<string> answer, map<string, map<string, int>, greater<string>>ticketsmap) {


    //사용한 티켓 기록
    answer.push_back(s.first);

   //이동한 간선수와 전체 간선의 수 비교
    if (num == ticketSize) { Aanswer = answer; return true; }

   //정렬된 간선 순서대로 이동
    for (auto s : ticketsmap[start]) {

    //간선이 존재하는가 확인
        if (s.second >0) {
        // 티켓 갯수 빼기
            ticketsmap[start][s.first]--;
            //재귀함수 실행 
            if (findAir(s.first, num + 1, answer, ticketsmap) == true) 
            {
                //true 반환시 탈출
                return true; 
            }
            else {
                //만약 현재 티켓대로 갔을경우 전부 소진하지 못할경우
                //티켓을 사용하지 않은 상태로 원복 시킨다
                ticketsmap[start][s.first]++;
            }
        }
    }

    //간선을 전부 돌았지만 티켓을 전부 사용하지 못했을경우 false 반환
    answer.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {

    string start = "ICN";
    map<string, map<string, int>> ticketsmap;
    for (int i = 0; i < tickets.size(); ++i)
    {
    //티켓 그래프 제작
        ticketsmap[tickets[i][0]][tickets[i][1]]++;
        ticketSize += 1;
    }
    vector<string> answer = {};

    findAir(start,0, answer, ticketsmap);

    return Aanswer;
}

아래와 같이 확인할수 있다

Step-by-Step Ticket Route Visualizer

+ Recent posts