ALOHA 월반 2주차 - 그래프 (DFS / BFS / Backtracking) 풀이

1. [19699] 소-난다! (Silver II)

의도한 태그: Backtracking (Easy)

소들을 선택하는 경우의 수는 \( {}_{N}C_{M} \)가지가 됩니다.

제한이 \( 1 \le M \le N \le 9 \)니, 조합의 식에서 분모를 아예 무시해도 \( 9! = 362 880 \)이라는, 충분히 작은 값이 나옵니다.

그러니, 이 경우들을 다 돌려보면 됩니다.

const int N = 9000; bool pr[9020];

int n, m; int arr[10]; vector<int> ans;
void btk(int idx, int cnt, int sum){
	if (idx > n){
		if (cnt == m){ if (pr[sum]){ ans.push_back(sum); } }
		return;
	}
	btk(idx+1, cnt, sum);
	btk(idx+1, cnt+1, sum+arr[idx]);
}

void Main(){
	memset(pr, 1, sizeof(pr)); pr[0] = pr[1] = 0;
	for (int i = 2; i <= N; i++){
		if (!pr[i]){ continue; }
		for (int j = i+i; j <= N; j+=i){ pr[j] = 0; }
	}
	cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	btk(1, 0, 0); unq(ans);
	if (ans.size() == 0){ cout << -1; }
	else{ for (int x : ans){ cout << x << ' '; } }
}

2. [6118] 숨바꼭질 (Silver I)

의도한 태그: BFS (Easy)

문제를 요약하자면, 최단경로가 가장 먼 점을 찾는 문제입니다.

 

그러니 1번 정점에서 출발해서 BFS로 모든 정점까지의 최단경로를 찾아준 뒤,

가장 가까운 점 / 그 점까지의 거리 / 그 점과 같은 거리를 가지는 점의 수를 찾아주면 됩니다.

vector<int> adj[20020];
int dis[20020];

void Main(){
	memset(dis, -1, sizeof(dis));
	int n, m; cin >> n >> m;
	while (m--){
		int v, w; cin >> v >> w;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	queue<pi2> q; q.push({1, 0}); dis[1] = 0;
	while (!q.empty()){
		int now = q.front().fr, dst = q.front().sc; q.pop();
		for (int nxt : adj[now]){
			if (dis[nxt] != -1){ continue; }
			q.push({nxt, dst+1}); dis[nxt] = dst+1;
		}
	}
	int mx = 0, mxp = 0, mxc = 0;
	for (int i = 1; i <= n; i++){
		if (mx < dis[i]){ mx = dis[i]; mxp = i; mxc = 0; }
		if (mx == dis[i]){ mxc += 1; }
	}
	cout << mxp << ' ' << mx << ' ' << mxc;
}

3. [1697] 숨바꼭질 (Silver I)

의도한 태그: BFS (Easy)

수빈이의 위치로 BFS를 돌려주면 됩니다.

간선은 문제에 나와있는대로 \( x+1, x-1, 2x \)에 연결해주면 됩니다.

 

범위를 넘어갔다가 돌아오는 게 가능하기 때문에, 탐색 범위를 적당히 충분하게 잡아주면 됩니다.

저는 자세한 거 생각하기 귀찮아서 최대 범위 × 2로 잡았습니다.

const int N = 200000; int dis[200020];

void Main(){
	memset(dis, -1, sizeof(dis));
	int st, ed; cin >> st >> ed;
	queue<pi2> q; q.push({st, 0}); dis[st] = 0;
	while (!q.empty()){
		int now = q.front().fr, dst = q.front().sc; q.pop();
		if (now == ed){ cout << dst; return; }
		for (int nxt : {now-1, now+1, 2*now}){
			if (0 > nxt || nxt > N){ continue; }
			if (dis[nxt] != -1){ continue; }
			q.push({nxt, dst+1}); dis[nxt] = dst+1;
		}
	}
}

 

4. [2239] 스도쿠 (Gold IV)

의도한 태그: Backtracking (Normal)

12095번 문제에 코드가 다 나와있습니다. (...) 심지어 저걸로 풀린다고 보장해줍니다. (내보지는 않았습니다.)

 

간단히 구현 방식을 설명하자면, 백트래킹을 돌리면서 수를 놓기 전에

• 가로줄에 같은 수가 있는지
• 세로줄에 같은 수가 있는지
• 3x3 박스에 같은 수가 있는지

판별해가면서 넣어주면 됩니다.

const int N = 9;
int mp[12][12], res[12][12];

bool row[12][12], col[12][12], box[12][12];
inline int bxi(int y, int x){ return (y-1)/3*3 + (x-1)/3 + 1; }
void btk(int y, int x){
	if (x > N){ y += 1; x = 1; }
	if (y > N){
		for (int i = 1; i <= N; i++){
			for (int j = 1; j <= N; j++){ cout << res[i][j]; }
			cout << endl;
		}
		exit(0);
	}
	if (mp[y][x] != 0){ return btk(y, x+1); }
	for (int d = 1; d <= 9; d++){
		if (row[y][d]){ continue; }
		if (col[x][d]){ continue; }
		if (box[bxi(y,x)][d]){ continue; }
		row[y][d] = col[x][d] = box[bxi(y,x)][d] = 1; res[y][x] = d; btk(y, x+1);
		row[y][d] = col[x][d] = box[bxi(y,x)][d] = 0; res[y][x] = 0;
	}
}

void Main(){
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			char ch; cin >> ch;
			mp[i][j] = ch-'0';
			if (mp[i][j] != 0){ int d = mp[i][j];
				row[i][d] = col[j][d] = box[bxi(i,j)][d] = 1;
				res[i][j] = d;
			}
		}
	}
	btk(1, 1);
}

5. [9019] DSLR (Gold IV)

의도한 태그: BFS (Normal)

0000부터 9999까지를 정점으로 생각해봅시다.

그럼, D S L R의 연산은 아래와 같이 생각해볼 수 있습니다.

• D (Double): \( 2x \)
• S (Subtract): \( (x-1) \text{ mod } 10000 \), 즉 \( (x+9999) \text{ mod } 10000 \)
• L (Left-shift): \( 10x \text{ mod } 10000 + \lfloor x/1000 \rfloor \)
• R (Right-shift): \( \lfloor x/10 \rfloor + 1000 \times (x \text{ mod } 10) \)

L, R 연산은 각 자리가 어떻게 이동하는지 생각해보면 왜 위 식이 되는지 볼 수 있습니다.

int dis[10020]; pic pre[10020];

void Main(){
	int t; cin >> t; while (t--){
		int st, ed; cin >> st >> ed;
		queue<int> q; q.push(st);
		memset(dis, -1, sizeof(dis)); dis[st] = 0;
		while (!q.empty()){
			int now = q.front(); q.pop();
			//cout << "Q " << now << endl << flush;
			pic p1 = { (now*2) % 10000, 'D' };
			pic p2 = { (now+9999) % 10000, 'S' };
			pic p3 = { (now*10)%10000 + (now/1000), 'L' };
			pic p4 = { (now/10) + (now%10)*1000, 'R' };
			for (pic p : {p1, p2, p3, p4}){
				int nxt = p.fr; char ch = p.sc;
				//cout << "NEXT " << nxt << ' ' << ch << endl << flush;
				if (dis[nxt] != -1){ continue; }
				dis[nxt] = dis[now] + 1; pre[nxt] = {now, ch};
				q.push(nxt);
			}
		}
		int ptr = ed; stack<char> ans;
		while (ptr != st){
			ans.push(pre[ptr].sc); ptr = pre[ptr].fr;
		}
		while (!ans.empty()){ cout << ans.top(); ans.pop(); } cout << endl;
	}
}

6. [2206] 벽 부수고 이동하기 (Gold IV)

의도한 태그: BFS (Normal)

격자점에서 BFS를 돌려봅시다. 그런데 이번에는 좌표만으로는 뭔가 부족한 것 같은 느낌이 됩니다.

'벽을 부순 횟수'가 추가적으로 저장되어있다면 이 문제를 충분히 풀 수 있을 것 같으니, 이를 저장해봅시다.

그러니까, \( D_{y, x, c} := (y, x) \)에서 벽을 \( c \)회 부숴서 이동할 때, 필요한 최소 이동 횟수 를 정의해봅시다.

그럼 BFS를 저대로 넣어서 풀어주면 됩니다.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};

int mp[1020][1020], dis[1020][1020][2];

void Main(){
	memset(dis, -1, sizeof(dis));
	queue<pi4> q;
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			char ch; cin >> ch; mp[i][j] = ch-'0';
		}
	}
	q.push({ {1, 1}, {0, 1} }); dis[1][1][0] = 1;
	while (!q.empty()){
		int y = q.front().fr.fr, x = q.front().fr.sc;
		int c = q.front().sc.fr, dst = q.front().sc.sc; q.pop();
		if (y==n && x==m){ cout << dst; return; }
		for (int k = 0; k < 4; k++){
			int yy = y+dy[k], xx = x+dx[k];
			if (1 > yy || yy > n){ continue; }
			if (1 > xx || xx > m){ continue; }
			int cc = c + mp[yy][xx];
			if (cc >= 2){ continue; }
			if (dis[yy][xx][cc] != -1){ continue; }
			q.push({ {yy, xx}, {cc, dst+1} }); dis[yy][xx][cc] = dst+1;
		}
	}
	cout << -1;
}

7. [17370] 육각형 우리 속의 개미 (Gold III)

의도한 태그: Backtracking (Hard)

딱히 특별한 건 없고, 가능한 개미의 이동을 다 해보면 됩니다.

 

구현은 육각형 좌표에서 인접한 칸을 아래와 같이 격자의 좌표로 변환해주는 방식을 쓰면 됩니다.

문제에서는 칸을 탐색하는 게 아니라 선을 탐색하는 거지만, 기본적인 아이디어는 동일합니다.

 

+ 문제에서는 시작 방향이 고정되어있는데, 저는 그걸 고려하지 않았던 덕분에 답에서 3을 나눠줬습니다.

const int dy[3] = {-1, 0, 1}, dx[3] = {0, 1, -1};

int n; int ans = 0;
int chk[50][50];
void dfs(int cnt, int y, int x){ if (cnt > n){ return; }
	chk[y][x] = cnt;
	for (int d = 0; d < 3; d++){
		int yy = y + (cnt&1 ? dy[d] : -dy[d]), xx = x + (cnt&1 ? dx[d] : -dx[d]);
		if (chk[yy][xx] == cnt-1){ continue; }
		else if (chk[yy][xx] != -1){ ans += (cnt==n); continue; }
		dfs(cnt+1, yy, xx); chk[yy][xx] = -1;
	}
}

void Main(){
	memset(chk, -1, sizeof(chk));
	cin >> n; n += 1; dfs(1, 25, 25);
	cout << ans/3;
}

8. [1167] 트리의 지름 (Gold II)

의도한 태그: DFS (Hard)

아무 정점이나 잡고 dfs를 돌려서 최장경로에 해당하는 정점을 찾은 뒤, 그 정점에서 출발하는 최장경로가 트리의 지름이 됩니다.

 

증명은 코드 밑에 자세히 적어두겠습니다.

vector<pl2> adj[100020];

pl2 res;
void dfs(int now, int pre, ll dis){
	res = max(res, mkp(dis, (ll)now));
	for (pl2 p : adj[now]){
		int nxt = p.fr, dst = p.sc;
		if (nxt == pre){ continue; }
		dfs(nxt, now, dis+dst);
	}
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		int v; cin >> v;
		while (1){
			int w, x; cin >> w; if (w == -1){ break; }
			cin >> x; adj[v].push_back({w, x});
		}
	}
	res = {0, 0}; dfs(1, 1, 0); int v = res.sc;
	res = {0, 0}; dfs(v, v, 0); cout << res.fr;
}

증명 전 잠시 짚고 넘어갈 점은, (당연하지만) 트리의 지름의 두 끝점은 리프 정점이어야 합니다.

이제 증명을 해봅시다. 이는 두 경우로 나눠서 귀류법을 통해 증명할 수 있습니다.

두 증명 모두에 대해서, 정점 \( a \)를 첫 dfs를 돌린 뒤 찾은 정점, \( a \leftrightarrow b \)를 코드가 찾은 지름,

\( c \leftrightarrow d \)를 실제 지름이라고 두겠습니다.

 

(증명에서는 편의상 "선택되지 않습니다"라고 하지만, 실제로는 "선택되지 않거나 / 선택되더라도 답에 영향을 끼치지 않는다"입니다.)

 

경우 1. \( a \leftrightarrow b \)와 \( c \leftrightarrow d \)가 1개 이상의 정점을 공유하고 있는 경우

a, b, c, d 정점 뒤에 1번 정점이 있다면 (a, b, c, d)가 리프 정점임에 위배되므로, 위 경우만 고려해주면 됩니다.

이 때, 지름의 정의에 의해 \( D_{a, v} + D_{w, b} < D_{c, v} + D_{w, d} \)가 됩니다.

그 외에도, 두 점의 경로 길이를 잡으면, 항상 \( D_{c, d} = D_{c, v} + D_{v, w} + D_{w, d} \)보다 작거나 같은 값을 가지게 됩니다.

 

또한, \( D_{a, v} \le D_{c, v} \)이고, \( D_{b, w} \le D_{d, w} \)여야 합니다.

그렇지 않다면 각각 \( c \)를 \( a \)로 / \( d \)를 \( b \)로 변경해서 더 긴 지름을 찾을 수 있기 때문이죠.

 

또한, 위 그림에는 편의상 저 바깥으로 뻗는 선들이 없는데, 그게 있다고 하더라도 그림에 그려진 선 위의 점으로 이동시켜줄 수 있기 때문에 (이 때 모두와의 거리가 1 감소해서 아래 식을 동일하게 적용 가능) 추가적으로 다루지 않아도 됩니다.

 

경우 1-1. \( v \leftrightarrow w \)에 1번 정점이 있는 경우

이 경우, \( D_{1, a} = D_{1, v} + D_{v, a} \le D_{1, v} + D_{v, c} = D_{1, c} \)이므로 \( a \)가 선택되지 않습니다.

 

경우 1-2. \( a \leftrightarrow v \)에 1번 정점이 있는 경우

\( D_{1, a} \le D_{v, a} \le D_{v, c} \le D_{1, c} \)이므로, \( a \)가 선택되지 않습니다.

 

경우 1-3. \( c \leftrightarrow v \)에 1번 정점이 있는 경우

\( D_{c, a} = D_{c, 1} + D_{1, v} + D_{v, a} \le D_{c, 1} + D_{1, v} + D_{v, w} + D_{w, d} = D_{c, d} \)이고,

이는 곧 \( D_{1, a} \le D_{1, d} \)임을 의미하므로 \( a \)가 선택되지 않습니다.

 

경우 1-4. \( b \leftrightarrow d \)에 1번 정점이 있는 경우

\( D_{1, a} = D_{1, w} + D_{w, v} + D_{v, a} \le D_{1, w} + D_{w, v} + D_{v, c} = D_{1, c} \)이므로 \( a \)가 선택되지 않습니다.

 

경우 2. \( a \leftrightarrow b \)와 \( c \leftrightarrow d \)가 정점을 공유하지 않는 경우

a, b, c, d 정점 뒤에 1번 정점이 있다면 (a, b, c, d)가 리프 정점임에 위배되므로, 위 경우만 고려해주면 됩니다.

지름의 정의에 의해 \( D_{c, d} \ge D_{x, y} \text{ forall } (x, y) \)입니다.

또한, \( D_{a, w} = D_{a, v} + D_{v, w} \le D_{w, c} \)입니다.

그렇지 않다면, \( d \rightarrow w \rightarrow c \)의 경로가 \( d \rightarrow w \rightarrow v \rightarrow a \)보다 더 짧기 때문이죠.

 

경우 2-1. \( a \leftrightarrow w \)에 1번 정점이 있는 경우

\( D_{1, a} \le D_{a, w} \le D_{w, c} \le D_{1, c} \)이므로 \( a \)가 선택되지 않습니다.

 

경우 2-2. \( c \leftrightarrow w \)에 1번 정점이 있는 경우

\( D_{c, a} = D_{c, 1} + D_{1, w} + D_{w, v} + D_{v, a} \le D_{c, 1} + D_{1, w} + D_{w, d} = D_{c, d} \),

즉 \( D_{1, a} = D_{1, w} + D_{w, v} + D_{v, a} \le D_{1, w} + D_{w, d} = D_{1, d} \)이므로 \( a \)가 선택되지 않습니다.

 

경우 2-3. \( b \leftrightarrow v \) 또는 \( d \leftrightarrow w \)에 1번 정점이 있는 경우

각각 \( v \) / \( w \)번 정점으로 이동을 시키면, \( D_{1, a} \)와 \( D_{1, c} \)가 1씩 줄어듭니다.

그러다가 \( v \) or \( w \)번 정점에 닿게 된다면, 경우 2-1로 오게 됩니다.

그런데 두 거리의 대소 관계가 바뀌지 않으니, 경우 2-1의 식으로 처리할 수 있게 됩니다.

9. [17501] 수식 트리 (Gold I)

의도한 태그: DFS (Hard)

트리를 펼쳐서 수식을 써보면, 각 항은 계수로 +1을 가지거나 -1을 가집니다.

그러니, 트리를 탐색하면서 현재 정점의 계수가 +1인지 -1인지를 들고 있으면,

최종 수식에서의 +1의 개수와 -1의 개수를 알 수 있게 됩니다.

 

계수의 부호를 바꾸는 건 '-'의 오른쪽 서브트리를 방문할 때에만 해주면 됩니다. (\( a - b \)에서 \( b \)의 위치)

 

실제 배치는, 자명하게 값이 큰 걸 +1에 넣고 / 작은 걸 -1에 넣어주면 됩니다.

ll arr[100020];
pci2 ptr[200020]; bool chk[200020];

int c1=0, c2=0;
void dfs(int now, int sgn){
	if (ptr[now].fr == 0){ (sgn == 1 ? c1 : c2) += 1; return; }
	dfs(ptr[now].sc.fr, sgn); dfs(ptr[now].sc.sc, (ptr[now].fr == '+' ? sgn : -sgn));
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = n+1; i < n+n; i++){
		cin >> ptr[i].fr >> ptr[i].sc.fr >> ptr[i].sc.sc;
		chk[ ptr[i].sc.fr ] = chk[ ptr[i].sc.sc ] = 1;
	}
	int r = 1; while (chk[r]){ r += 1; }
	dfs(r, 1);
	sort(arr+1, arr+n+1);
	ll ans = 0;
	for (int i = 1; i <= c2; i++){ ans -= arr[i]; }
	for (int i = c2+1; i <= n; i++){ ans += arr[i]; }
	cout << ans;
}