그래프 (2) 문제들

 

 

 

2593 Elevator    BFS DP

N층짜리 건물에서 주어진 수열의 층에서만 멈추는 엘레베이터가 M대 있을 때

A층에서 B층까지 가기 위해 최소한으로 갈아타는 엘레베이터의 수 & 내렸던 층을 구한다.

트래킹때문에 좀 복잡했던 문제같음..

 

현재 층 curf에서 탈 수 있는 엘레베이터 cure

cure에서 내릴 수 있는 다음 층 nxtf

nxtf가 B와 같다면 종료

다르다면 nxtf를 큐에 넣고 다음 엘레베이터 nxte로 갈아타며 dp를 업데이트

	// Initiate
	for (int e : f[A]) dp[A][e] = { 1,0 };
	Q.push(A);

	// BFS and Get Ans
	bool arrived_at_B = false;
	while (!Q.empty()) {
		arrived_at_B = false;

		int curf = Q.front(); Q.pop();
		for (int cure : f[curf]) {
			cnt = dp[curf][cure].first;

			//cure로 갈 수 있는 층 nxtf
			int k = E[cure].second;
			for (int nxtf = E[cure].first; nxtf <= N; nxtf += k) {
				if (nxtf == curf || dp[nxtf][cure].first) continue;

				dp[nxtf][cure] = { cnt,curf };
				if (nxtf == B) {
					S.push({ B,cure }); arrived_at_B = true; break;
				}
				Q.push(nxtf);

				//nxtf에서 갈아탄 nxte
				for (int nxte : f[nxtf]) {
					if (nxtf == curf || dp[nxtf][nxte].first) continue;

					dp[nxtf][nxte] = { cnt + 1, curf };
				}
			}
			if (arrived_at_B) break;
		}
		if (arrived_at_B) break;
	}

BFS에서 pair<int,int>를 썼었다가 int만 써도 해결할 수 있음을 알았다.

 

 

 

 

16946 벽 부수고 이동하기 4   BFS DFS Disjoint Set(?)

현재 위치의 상하좌우에 위치한 벽을 부쉈을 때 움직일 수 있는 칸의 수를 구하는 문제

BFS로 구간 구해서 동서남북 잘 더해주면 된다.

예전에 틀려서 방치해두다가 틀린 문제 고쳤다.

 

 

 

 

16724 피리부는 사나이   DFS Disjoint Set

움직임을 계속하다보면 도는 구간만 돌게 되는데 그 구간의 개수를 찾는 문제

 

 

 

 

1948 임계경로   위상정렬

시작점에서 도착점까지 모든 경로를 거쳐 가면서 가장 오래 걸리는 길을 찾는다.

초반에 다익스트라로 생각했다가 틀렸습니다 맞고 찾아보니 위상정렬,,,,

 

	Q.push(D);
	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();

		for (edge e : E[cur]) {
			int cost = maxcost[cur] + e.c;
			if (cost > maxcost[e.v]) maxcost[e.v] = cost, from[e.v].clear();
			if (cost == maxcost[e.v]) from[e.v].push_back(cur);

			ind[e.v]--;
			if (!ind[e.v]) Q.push(e.v); //위상정렬
		}
	}