백준 3184 양

설계:

• map상 obj인 울타리, 양, 늑대의 존재여부를 나타내는 bool 2차원 배열 선언 vs map 2차원 배열 선언
  • 전자는 한 위치에 여러 obj 존재 가능할 경우 유용 vs 후자는 한 위치에 하나의 obj만 존재 가능할 경우 유용

수정:

• 탐색시 '기방문 위치 skip' 누락
• switch의 각 case별 break 누락

소요시간:

 

개선:

• 방문 여부를 나타내는 별도 배열 선언 대신 map에 '#'로 표시
• map상 모든 위치에 대해 탐색하는 대신 'o', 'v'가 존재하는 위치만 탐색

 

// BFS버전
#include <stdio.h>
#include <utility>
#include <queue>

using namespace std;

int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

#define IN_MAP(r, c) (0 <= r && r < R && 0 <= c && c < C)

void BFS(int m[][250], int r, int c, int R, int C, int &s, int &w) {
	switch (m[r][c]) {
	case 'o': ++s; break;
	case 'v': ++w; break;
	}

	pair<int, int> rt = { r, c };
	m[r][c] = '#';
	queue<pair<int, int>> q;
	q.push(rt);

	while (!q.empty()) {
		pair<int, int> pt = q.front();
		q.pop();

		for (int d = 0; d < 4; ++d) {
			int cr = pt.first + dr[d], cc = pt.second + dc[d];

			if (!IN_MAP(cr, cc))
				continue;

			switch (m[cr][cc]) {
			case '#': continue;
			case 'o': ++s; break;
			case 'v': ++w; break;
			}

			m[cr][cc] = '#';
			pair<int, int> cd = { cr, cc };
			q.push(cd);
		}
	}
}

int main() {
	int R, C;
	scanf("%d%d", &R, &C); getchar();

	int m[250][250];
	pair<int, int> sw[62500];
	pair<int, int> *swp = sw;
	for (int r = 0; r < R; ++r) {
		for (int c = 0; c < C; ++c) {
			m[r][c] = getchar();	/* 그대로 받기 */
			switch (m[r][c]) {
			case 'o': case 'v':
				*(swp++) = make_pair(r, c); break;
			}
		} getchar();
	}

	int ts = 0, tw = 0;
	for (int i = 0; sw + i < swp; ++i) {
		int r = sw[i].first, c = sw[i].second;

		if (m[r][c] == '#')
			continue;

		int ps = 0, pw = 0;
		BFS(m, r, c, R, C, ps, pw);
		if (ps > pw) ts += ps;	// sheep이겨서 total wolf에서 partial wolf 제거
		else		 tw += pw;	// wolf이겨서 total sheep에서 partial sheep 제거
	}

	printf("%d %d", ts, tw);

	return 0;
}

// DFS
#include <stdio.h>
#include <utility>

using namespace std;

int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

#define IN_MAP(r, c) (0 <= r && r < R && 0 <= c && c < C)

bool DFS(int m[][250], int r, int c, int R, int C, int &s, int &w) {
	m[r][c] = '#';

	for (int d = 0; d < 4; ++d) {
		int nr = r + dr[d], nc = c + dc[d];

		if (!IN_MAP(nr, nc))
			return 1;

		switch (m[nr][nc]) {
		case '#': continue;
		case 'o': ++s; break;
		case 'v': ++w; break;
		}

		if (DFS(m, nr, nc, R, C, s, w))
			return 1;
	}
	return 0;
}

int main() {
	int R, C;
	scanf("%d%d", &R, &C); getchar();

    pair<int, int> sw[62500];
    pair<int, int> *swp = sw;
	int m[250][250];
	for (int r = 0; r < R; ++r) {
		for (int c = 0; c < C; ++c) {
			m[r][c] = getchar();
            switch(m[r][c]){
                case 'o': case 'v':
                    *(swp++) = make_pair(r, c); break;
            }
		} getchar();
	}

    int ts = 0, tw = 0;
	for (int i = 0; sw + i < swp; ++i){
            int r = sw[i].first, c = sw[i].second;
        
			if (m[r][c] == '#')
				continue;

			int ps = 0, pw = 0;
			switch (m[r][c]) {
			case 'o': ++ps; break;
			case 'v':  ++pw; break;
			}
			DFS(m, r, c, R, C, ps, pw);
			
			if (ps > pw) ts += ps;	// sheep이겨서 total wolf에서 partial wolf 제거
			else		 tw += pw;	// wolf이겨서 total sheep에서 partial sheep 제거
	}

	printf("%d %d", ts, tw);

	return 0;
}