[풀이]백준 풀이(VI/16929), SW EA(1767)

문제풀이

[RE]Two Dots(16929, DFS, O(N*M))

  • 사이클의 정의 (같은 색, 4개 이상 연결된 점들의 집합)
  • 즉, 임의의 점에서 시작해서 길이가 4이상인 도착점(자기자신)이 있는지만 확인.
  • DFS, BFS 모두 가능.

풀이1. 마지막 정점에서 find를 한 뒤 이미 방문했던 같은 색상의 점이 있다면 사이클이 존재. (일단 갔던 곳도 방문을 해 본 뒤, 뺄셈)

풀이2. 이전 칸과 다른 칸만 방문해서 이미 방문했던 곳으로 돌아오게 될 경우 사이클은 무조건 존재한다.

TIP: 다른 점에서 DFS를 다시 시작 할 경우 CHECK배열을 초기화할 필요가 없다.(사이클이 있었으면 이미 끝났고 다시 본다고 해도 사이클이 생기지도 않음).

회고

  1. 좀 다른 방식으로 푼 것 같다.
  2. 수업 내용 중 중복을 줄이기 위해 이미 갔던곳은 반복하지 않는 경우가 있었던 것이 기억나 memset을 안해서 답이 틀렸었다.

YYYR
BYBY
BBBY
BBBY

의 경우 (1,0)의 B에서 시작하면 마지막 조건문 sx==cx && sy==cy에 걸리지 않고 다른 점들을 모두 방문한 노드로 변경해버렸었다..

디버깅은 참 좋은 기능이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m, sx, sy;
bool check[51][51];
char map[51][51];
bool fin;
int dx[] = {0,  0, 1, -1 };
int dy[] = {1, -1, 0,  0 };

void dfs(int x, int y, char color, int count){

	if(fin) return;
	for(int i=0; i<4; i++){
		int cx = x + dx[i];
		int cy = y + dy[i];
		if(cx>=0 && cx<n && cy>=0 && cy<m)
		{
			if(!check[cx][cy])
			{
				if(map[cx][cy] == color)
				{
					check[cx][cy] = true;
					dfs(cx,cy, color, count+1);
				}
			}
			else
			{
				if(count >=4 && sx == cx && sy ==cy)
				{
					fin = true;
					return;
				}
			}

		}
	}
}

int main(){
	cin >> n >> m;

	//입력
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			char a;
			cin >> a;
			map[i][j] = a;
		}
	}
	//dfs 실행
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			memset(check, false, sizeof(check));
			sx = i; sy = j;
			check[i][j]=true;
			int cnt =1;
			dfs(i,j, map[i][j], cnt);
			if(fin)
			{
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

[RE] 프로세서 연결하기 (SW 아카데미)

  • N * N 의 행렬 (CORE 혹은 전선이 들어갈 수 있다.)
  • (7<=N<=12), (1<=num of CORE<=12), 연결되지 않는 코어 허용
  • 행렬의 가장자리에는 전원이 흐르고 있다. (가장자리에 위치한 코어는 전선이 필요없다.)
  • core와 전원을 연결하는 전선은 직석으로만 설치가 가능하다.
  • 전원은 교차할 수 없다.
  • 최대한 많은 Core에 전원을 연결한 경우 전선 길이의 합은? (같은 Core 개수가 있다면 전선길이가 최소인 것을 출력)

방법 생각하기

  • Core의 개수가 주어지므로 각 코어에서 DFS를 돌리면 될 것 같은데..
  • 순차적으로 DFS/BFS를 진행하며 지나갔던 길은 CHECK한다.
  • 문제는 DFS, BFS의 목적지 NODE를 무엇으로 하느냐 인 것 같다.

풀이 1. 선택한 1에서 갈 수 있는 모든 모서리를 다 본다.

N의 최대가 12이므로 4^12 = 2^24 = 16777216(2천만) 타임아웃이 안난다.

  • 가장자리 코어는 따로 카운트
  • 나머지 코어에 들은

DFS부분부터 다시짜기


#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;


int N, Answer=INF, nx, ny;
bool check[13][13];
int map[13][13], dist[13];
char direction[4] = { 'U', 'D', 'L', 'R' };
vector<pair<int, int>> core;

bool isConnection(int x, int y, char direction) {

	if (direction == 'D' )
	{
		for (int j = x + 1; j < N; j++) {
			if (map[j][y]) return false;
		}

		//위쪽에 갈 수 있는 길이 있다. - 지나간다
		for (int j = x + 1; j < N; j++) {
			map[j][y] = 2;
		}
		return true;
	}
	if (direction == 'U')
	{
		for (int j = x - 1; j >= 0; j--) {
			if (map[j][y]) return false;
		}

		for (int j = x - 1; j >= 0; j--) {
			map[j][y] = 2;
		}
		return true;
	}
	if (direction == 'R')
	{
		for (int j = y + 1; j < N; j++) {
			if (map[x][j]) return false;
		}

		for (int j = y + 1; j < N; j++) {
			map[x][j] = 2;
		}
		return true;
	}
	if (direction == 'L')
	{
		for (int j = x; j < N; j++) {
			if (map[j][y]) return false;
		}

		for (int j = x; j < N; j++) {
			map[x][j] = 2;
		}
		return true;
	}

}

bool isEdge(int x, int y) {
	if (x == 0 || x == N - 1 || y == 0 || y == N - 1) return true;
	else return false;
}


void init() {
	for (int j = 0; j < N; j++) {
		for (int k = 0; k < N; k++) {
			map[j][k] = 0;
			check[j][k] = false;
		}
	}
}

int calcDist() {
	int dist = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 2) dist++;
		}
	}
	return dist;
}
bool find_next(int x, int y) {

	for (int i = 0; i < core.size(); i++) {
		if (core[i].first == x && core[i].second==y) {
			if (i == core.size() - 1) 
			{
				Answer = min(Answer, calcDist());
				return false;
			}
			nx = core[i + 1].first;
			ny = core[i + 1].second;
			return true;
		}
	}
}
void dfs(int x, int y) {

	//if(조건을 만족하면) 종료

	//전선은 오직 직선, 4방향 모두 확인
	for (int i = 0; i < 4; i++) {
		//예외1. 현재 위치(x,y)가 가장자리인 경우
		if (isEdge(x, y))
		{
			find_next(x, y);
			dfs(nx, ny);
		}
		else
		{
			//온 적이 없으면
			if (!check[x][y]) 
			{
				//만약 U, D, L, R 중 갈 수 있는 곳이 있는지 확인 후 변경
				if (isConnection(x, y, direction[i])) 
				{
					//노드 위치 체크
					check[x][y] = true;
					if (find_next(x, y)) dfs(nx, ny);
					else return;

				}

			}
		}
	}
}



int main(void) {

	int test_case;
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		cin >> N;


		//초기화
		init();

		//입력
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				cin >> map[j][k];
				if (map[j][k]) core.push_back(make_pair(j, k));

			}
		}

		for (int i = 0; i < core.size(); i++) {
			dfs(core[i].first, core[i].second);

			init();
		}
	}
}

  • 전체 길이는 나중에 check에 1인 녀석들을 다 합치면 된다 :)

  • 문제1. map을 boolean으로 하다보니 map이 갱신될 때마다 코어와 길을 구분할 수가 없었다. - 타입변경

  • 문제2. 연결된 코어의 개수를 우선순위로 하는 코드가 빠짐

  • 문제3. 방향별로 돌 때 map을 갱신하는 것을 잊음..

예제실수 ㅎㅎ..


#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;


int n, nx, ny, pnum, res;
int map[13][13], dist[13];
char direction[4] = { 'U', 'D', 'L', 'R' };

bool isLine(int x, int y, int dir) {
	//0동,1남,2서,3북

	if (dir == 0) {
		for (int i = y + 1; i < n; i++) {
			if (map[x][i] != 0)return false;
		}
	}
	else if (dir == 1) {
		for (int i = x + 1; i < n; i++) {
			if (map[i][y] != 0)return false;
		}
	}
	else if (dir == 2) {
		for (int i = 0; i < y; i++) {
			if (map[x][i] != 0)return false;
		}
	}
	else {
		for (int i = 0; i < x; i++) {
			if (map[i][y] != 0) return false;
		}
	}


	return true;


}

int draw_line(int x, int y, int dir, int flag) {
	int ans = 0;
	if (dir == 0) {
		for (int i = y + 1; i < n; i++) {
			map[x][i] = (flag == 0) ? 2 : 0;
			ans++;
		}
	}
	else if (dir == 1) {
		for (int i = x + 1; i < n; i++) {
			map[i][y] = (flag == 0) ? 2 : 0;
			ans++;
		}
	}
	else if (dir == 2) {
		for (int i = 0; i < y; i++) {
			map[x][i] = (flag == 0) ? 2 : 0;
			ans++;
		}
	}
	else {
		for (int i = 0; i < x; i++) {
			map[i][y] = (flag == 0) ? 2 : 0;
			ans++;
		}
	}
	return ans;
}



void dfs(vector<pair<int,int>> &v, int idx, int num, int line) {

	if (idx == v.size()) {
		// 최대프로세서 갯수가 갱신되는 경우
		if (pnum < num) {
			res = line;
			pnum = num;
		}
		// 최대프로세서 갯수가 같은 경우
		else if (pnum == num) {
			if (res > line) res = line;
		}
	}
	else {
		// 4방향에대해 라인놓기 시도 + 라인 놓지않고 다음 프로세서로 넘어가는 경우
		// 총 5가지에 대해 탐색
		for (int i = 0; i < 4; i++) {
			if (isLine(v[idx].first, v[idx].second, i)) {
				dfs(v, idx + 1, num + 1, line + draw_line(v[idx].first, v[idx].second, i, 0));
				draw_line(v[idx].first, v[idx].second, i, 1);
			}
		}
		dfs(v, idx + 1, num, line);
	}
}

int main(void) {
	int test_case;
	cin >> test_case;

	for (int i = 1; i <= test_case; i++) {
		cin >> n;
		vector<pair<int,int>> core;
		
		//입력
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				cin >> map[j][k];
				//여기 인풋 받는데가 문제였다.
				//if (i == 0 || j == 0 || i == n - 1 || j == n - 1) continue;
				if (j == 0 || k == 0 || j == n - 1 || k == n - 1) continue;
				if (map[j][k]) core.push_back(make_pair(j, k));
			}
		}

		res = INF;
		pnum = 0;
		dfs(core,0, 0, 0 );
		cout << "#" << i << " " << res <<endl;
	}
}

댓글남기기

참고