[BOJ] 백준 14502 연구소 c++

BOJ 문제 링크: https://www.acmicpc.net/problem/14502

14502번: 연구소

연구소가 N*M크기 행렬로 주어진다. 연구소 각 칸의상태는 빈칸(0), 벽(1), 바이러스(2) 세가지 중 하나이다.

바이러스가 아직 퍼지지 않은 상태지만, 바이러스가 벽에 막히지 않는다면 상하좌우로 인접한 빈 칸에 퍼져 나갈 예정이다.

벽을 꼭 3개 세워서 바이러스가 퍼져나가는것을 막는다 했을때, 빈칸으로 남을 수 있는 안전영역 크기의 최댓값을 구하는 문제이다.

 

3개의 벽을 세우는 모든 경우를 구하고, 각 경우마다 바이러스가 퍼졌을때 0으로 남아있는 칸의 갯수를 구하는 식으로 문제를 풀 수있다.

벽을 세울때는 N*M개의 각 칸들을 일차원으로 풀어서 here로 표현한다.

현재영역(here)이 0이면 here에 벽을 설치하거나, 설치안하거나 두가지 경우를 계산하고 here이 0이 아니면 바로 다음칸(here+1)로 넘어간다.

안전영역의 넓이를 구할때는 bfs를 이용하는데 연구소상태(lab)를 훼손시키면 안되므로

visited라는 이차원 배열을 따로 두어서 바이러스가 이미 퍼진곳인지, 아직 퍼지지 않은 곳인지 표현한다.

 

 

코드 원본: https://github.com/sbl133/BOJ/blob/main/%2314502.cpp

GitHub - sbl133/BOJ

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!