<div id="readability-page-1" class="page"><div><h2 id="문제"><a href="#%EB%AC%B8%EC%A0%9C" aria-label="문제 permalink"></a>문제</h2>
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
<h2 id="입력"><a href="#%EC%9E%85%EB%A0%A5" aria-label="입력 permalink"></a>입력</h2>
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
<h3 id="출력"><a href="#%EC%B6%9C%EB%A0%A5" aria-label="출력 permalink"></a>출력</h3>
첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.
<h3 id="코드"><a href="#%EC%BD%94%EB%93%9C" aria-label="코드 permalink"></a>코드</h3>
<ol>
<li>n,m과 board배열 입력</li>
<li>그림이 아니거나(board[i][j] == 0) 방문한 적 있을 때(isVisit[i][j] == 1) → <code>continue</code></li>
<li>
방문하지 않은 그림일 때
<ol>
<li><code>picNum++;</code> → 상하좌우 더이상 연결된 것이 없는 범위까지가 그림임</li>
<li><code>queue</code> 를 만들어서 방문하지 않은 좌표들을 담는다.</li>
<li><code>queue</code>에 삽입했다면 <code>isVisit</code>에 해당 좌표 방문처리를 한다.</li>
<li>최신 좌표를 꺼낸 후, 큐에서 삭제한다.</li>
<li>최신 좌표의 상하좌우를 돌며, 방문하지 않은 그림의 좌표를 큐에 삽입한다.</li>
<li>큐가 전부 빌 때 까지 반복</li>
</ol>
</li>
</ol>
<div data-language="cpp"><pre><code>#include&lt;bits/stdc++.h&gt;
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int board[502][502];
bool isVisit[502][502];
int n, m;
int main() 
{
 ios::sync_with_stdio(0);
 cin.tie(0);
 cin &gt;&gt; n &gt;&gt; m;
 for(int i=0;i&lt;n;i++) {
 for(int j=0;j&lt;m;j++) {
 cin &gt;&gt; board[i][j];
 }
 }
 int picNum = 0; // 그림의 수
 int maxPic = 0; // 그림 최댓값
 for(int i=0;i&lt;n;i++) {
 for(int j=0;j&lt;m;j++) {
 // 그림이 아니거나 방문한 적 있는 경우
 if(board[i][j] == 0 || isVisit[i][j]) continue;
 picNum++;
 queue&lt;pair&lt;int, int&gt;&gt; q;
 isVisit[i][j] = 1;
 q.push({i, j});
 int area = 0; // 그림의 넓이
 // 인접 칸을 다 돌 때 까지
 while(!q.empty()) {
 area++;
 pair&lt;int, int&gt; current = q.front();
 q.pop();
 for(int dir=0;dir&lt;4;dir++) {
 int nearX = current.first + dx[dir];
 int nearY = current.second + dy[dir];
 if(nearX &lt; 0 || nearX &gt;=n || nearY &lt;0 || nearY &gt;=m) continue;
 if(isVisit[nearX][nearY] || board[nearX][nearY]!=1) continue;
 isVisit[nearX][nearY] = 1;
 q.push({nearX, nearY});
 }
 }
 // (i, j) 를 시작점으로 하는 BFS 종료
 maxPic = max(maxPic, area);
 }
 }
 cout &lt;&lt; picNum &lt;&lt; "\\n" &lt;&lt; maxPic;
 return 0;
}</code></pre></div></div></div>

Seulog💘

이예슬

문제
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
입력
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
출력
첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.
코드
n,m과 board배열 입력
그림이 아니거나(board[i][j] == 0) 방문한 적 있을 때(isVisit[i][j] == 1) → continue
방문하지 않은 그림일 때
picNum++; → 상하좌우 더이상 연결된 것이 없는 범위까지가 그림임
queue 를 만들어서 방문하지 않은 좌표들을 담는다.
queue에 삽입했다면 isVisit에 해당 좌표 방문처리를 한다.
최신 좌표를 꺼낸 후, 큐에서 삭제한다.
최신 좌표의 상하좌우를 돌며, 방문하지 않은 그림의 좌표를 큐에 삽입한다.
큐가 전부 빌 때 까지 반복
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int board[502][502];
bool isVisit[502][502];
int n, m;
int main() 
{
 ios::sync_with_stdio(0);
 cin.tie(0);
 cin >> n >> m;
 for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 cin >> board[i][j];
 }
 }
 int picNum = 0; // 그림의 수
 int maxPic = 0; // 그림 최댓값
 for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 // 그림이 아니거나 방문한 적 있는 경우
 if(board[i][j] == 0 || isVisit[i][j]) continue;
 picNum++;
 queue<pair<int, int>> q;
 isVisit[i][j] = 1;
 q.push({i, j});
 int area = 0; // 그림의 넓이
 // 인접 칸을 다 돌 때 까지
 while(!q.empty()) {
 area++;
 pair<int, int> current = q.front();
 q.pop();
 for(int dir=0;dir<4;dir++) {
 int nearX = current.first + dx[dir];
 int nearY = current.second + dy[dir];
 if(nearX < 0 || nearX >=n || nearY <0 || nearY >=m) continue;
 if(isVisit[nearX][nearY] || board[nearX][nearY]!=1) continue;
 isVisit[nearX][nearY] = 1;
 q.push({nearX, nearY});
 }
 }
 // (i, j) 를 시작점으로 하는 BFS 종료
 maxPic = max(maxPic, area);
 }
 }
 cout << picNum << "\\n" << maxPic;
 return 0;
}

[백준]Q1926

댓글