๋ฌธ์
์ ๊ดํ ์ ๊ตฌ ์กฐ์
์ฒซ์งธ ์ค์ ์ ๊ดํ์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ์ธ๋ก ๊ธธ์ด $M$๊ณผ ๊ฐ๋ก ๊ธธ์ด $N$์ด ์ ๋ ฅ๋๋ค. ($2<=M,N<=100$์ธ ์์ฐ์) ๋์งธ์ค ๋ถํฐ $M$์ค์ ๊ฑธ์ณ $N$์ด ๋งํผ์ ์ ๊ตฌ๋ค์ ์ํ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ ์ผ์ง ์ํ๋ $1$, ๊บผ
codeup.kr
์ฝ๋
#include <iostream> #include <queue> using namespace std; int N,M; int map[101][101]; int visited[101][101]; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int right_on = 0,right_off=0; void go_rignt_on(int x, int y){ queue<pair<int,int>>q; q.push({x,y}); visited[x][y]=1; while(!q.empty()){ int x=q.front().first; int y=q.front().second; q.pop(); for(int i=0; i<4; i++){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx>=0&&nx<N&&ny>=0&&ny<M){ if(visited[nx][ny]||map[nx][ny]==1) continue; q.push({nx,ny}); visited[nx][ny]=1; } } } right_on++; } void go_rignt_off(int x, int y){ queue<pair<int,int>>q; q.push({x,y}); visited[x][y]=1; while(!q.empty()){ int x=q.front().first; int y=q.front().second; q.pop(); for(int i=0; i<4; i++){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx>=0&&nx<N&&ny>=0&&ny<M){ if(visited[nx][ny]||map[nx][ny]==0) continue; q.push({nx,ny}); visited[nx][ny]=1; } } } right_off++; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>N>>M; for(int i=0; i<N; i++){ for(int k=0; k<M; k++){ cin>>map[i][k]; } } for(int i=0; i<N; i++){ for(int k=0; k<M; k++){ if(map[i][k]==0&&!visited[i][k]) go_rignt_on(i,k); } } memset(visited,0,sizeof(0)); for(int i=0; i<N; i++){ for(int k=0; k<M; k++){ if(map[i][k]==1&&!visited[i][k]) go_rignt_off(i,k); } } cout<<right_on<<' '<<right_off; }
ํ์ด
๊ธฐ์ด์ ์ธ DFS/BFS ๋ฌธ์ ์์ต๋๋ค. ์ ์์ ์ผค ๋์ ์ ์์ ๋ ๋ ๊ฐ๊ฐ BFS๋ฅผ ๋๋ ค์ BFS๊ฐ ์ํํ๋ ์ดํ์๋ฅผ ์ถ๋ ฅํ๋ฉด ๋ฉ๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > CodeUp' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
1510 : ํ์ ๋ง๋ฐฉ์ง (0) | 2022.01.16 |
---|---|
4503 : ๋ฐ์ด๋ฌ์ค (0) | 2022.01.14 |
3705 : ์ฐ์๋ ๊ตฌ๊ฐ์ ์ต๋ํฉ (0) | 2022.01.14 |
3108 : ์ ์ฌ ์ฐธ์ฌ ํ์ ๋ฆฌ์คํธ ๋ง๋ค๊ธฐ 1 (0) | 2022.01.14 |
2641 : ์๋ค๋ฆฌ์ ๊ณ๋จ ์ค๋ฅด๊ธฐ (Small) (0) | 2022.01.14 |
2633 : Lower Bound (0) | 2022.01.14 |
๋๊ธ