글 읽기 - 삼성 상어문제 부족한 이해를 채우고 싶어요

luckyquit 4년 전 0

제가 생각한 논리대로 구현하였습니다. 주석을 참고하여 주세요

문제에 있는 건 다 구현을 했는데, TC조차 제대로 안 돌아가는게 몇개 있네요,,

어떤 부분이 빠졌다! 라는 걸 지적해주셨으면 합니다. 2시간째 고민했지만 역부족이었습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<cstring>
using namespace std;

typedef pair<int, int> pi;
queue<pair<pi,int>> q;

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

const int MAX_INT = 20, MAX_DIST = 41;
int shark_y, shark_x, shark_size = 2, eat_cnt, min_y, min_x, min_dist, n;

int map[MAX_INT][MAX_INT], check[MAX_INT][MAX_INT];

void init() 
{
	memset(check, 0, sizeof(check));
	min_y = min_x = MAX_INT;
	min_dist = MAX_DIST;
}

void bfs(int y, int x)
{
	queue<pi> q;
	q.push({ y,x });

	while (!q.empty()) {
		auto cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.first + dy[dir];
			int nx = cur.second + dx[dir];

			if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
			if (check[ny][nx] != 0 || map[ny][nx] > shark_size) continue;

			/* 거리 갱신 */
			check[ny][nx] += check[cur.first][cur.second] + 1;


			/* 먹을 수 있을 때 */
			if (map[ny][nx] != 0 && map[ny][nx] < shark_size) {
				
				/* 거리가 차이난다면 */
				if (min_dist > check[ny][nx]) {
					min_y = ny;
					min_x = nx;
					min_dist = check[ny][nx];
				}
				/* 거리가 같다면 */
				else if (min_dist == check[ny][nx]) {
					if (min_y == ny) {	// 높이가 같다면, 
						if (min_x > nx) {	// 가장 왼쪽에 있는 걸 먹어야함.
							min_y = ny;
							min_x = nx;
						}
					}	// 높이가 0에 가까울 수록 높은 것
					else if (min_y > ny)
						min_y = ny;
						min_x = nx;
				}

			}
			q.push({ ny,nx });
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int result = 0;

	cin >> n;
    
    /* y : 상하 x : 좌우 */
    // 0에 가까울수록 y는 상, x는 좌
	for (int y = 0; y < n; y++)
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
			if (map[y][x] == 9) {
				shark_y = y, shark_x = x;
				map[y][x] = 0;
			}
		}

	while (true) {
		init();
		bfs(shark_y, shark_x);

		if (min_y == MAX_INT || min_x == MAX_INT) break;

		else {

			result += check[min_y][min_x];	//위의 BFS에서 갱신한 값으로 result를 채운다
			eat_cnt++;

			if (eat_cnt == shark_size) {	// 같은 크기만큼 물고기를 먹었다면?
				shark_size++;
				eat_cnt = 0;
			}

			map[min_y][min_x] = 0;	// 해당자리를 편의를 위해 0으로 채운다

			/* 물고기를 먹었기때문에 그 자리로 이동시킨다. */
			shark_y = min_y; 
			shark_x = min_x;
		}
	}
	
	cout << result << '\n';
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

삼성 상어문제 부족한 이해를 채우고 싶어요

luckyquit 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말