BOJ 2573 빙산

2020. 11. 7. 00:47·알고리즘/BOJ

www.acmicpc.net/problem/2573

 

2573번: 빙산

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을

www.acmicpc.net

빙하가 2차원 배열로 주어지는데 빙하 상하좌우에 0이 있다면 빙하가 0 하나당 -1씩 줄어든다.

구현하면서 신경 쓸만한 부분은 날짜가 지남에 따라 빙하가 녹는 것, 빙하로 이루는 땅이 2개 이상인지 확인할 것

2개만 신경써주면 된다.

 

			if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--;
			else if (!vis[nx][ny]) {
				q.push({ nx,ny });
				vis[nx][ny] = true;
			}

 

상하좌우를 돌면서 방문하지 않았고 0이라면 현재 값을 1 줄여주고

방문하지 않은 빙하라면 큐에 넣어준다.

그리고 갱신해준 후 0 이하라면 0으로 수정해주면 된다.

 

#include <iostream>
#include <queue>
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> q;
int n, m, ans, ar[301][301];
bool vis[301][301];

void bfs(int x, int y) {
	vis[x][y] = true;
	q.push({ x,y });

	while (!q.empty()) {
		auto cur = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--;
			else if (!vis[nx][ny]) {
				q.push({ nx,ny });
				vis[nx][ny] = true;
			}
		}
		if (ar[cur.first][cur.second] < 0) 
			ar[cur.first][cur.second] = 0;
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> ar[i][j];

	while (1) {
		for (int i = 0; i < n; ++i) fill(vis[i], vis[i] + m, false);

		int land = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (vis[i][j] || !ar[i][j]) continue;
				bfs(i, j);
				land++;
			}
		}

		if (land > 1) break;
		else if (land == 0) {
			ans = 0; break;
		}
		ans++;
	}

	cout << ans << endl;

	return 0;
}

 

'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 1922 네트워크 연결  (0) 2020.11.14
BOJ 10282 해킹  (0) 2020.11.11
BOJ 4485 녹색 옷 입은 애가 젤다지?  (0) 2020.11.06
BOJ 1238 파티  (0) 2020.11.05
BOJ 9370 미확인 도착지  (0) 2020.11.05
'알고리즘/BOJ' 카테고리의 다른 글
  • BOJ 1922 네트워크 연결
  • BOJ 10282 해킹
  • BOJ 4485 녹색 옷 입은 애가 젤다지?
  • BOJ 1238 파티
khyu2
khyu2
  • khyu2
    dev log
    khyu2
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘
        • BOJ
        • Programmers
        • Algorithm
        • SWEA
      • 개발
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    크루스칼
    dfs
    트리
    SWEA
    피보나치 수
    행렬 제곱
    구현
    알고리즘
    시뮬레이션
    코딩테스트 연습
    냅색
    유니온 파인드
    조합
    완전탐색
    BFS
    dp
    프로그래머스
    완전 탐색
    MST
    GREEDY
    우선순위 큐
    다익스트라
    팰린드롬
    이분 탐색
    큐
    분할 정복
    소수
    이분탐색
    BOJ
    피사노 주기
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
khyu2
BOJ 2573 빙산
상단으로

티스토리툴바