[백준/c++] 4963번 섬의 개수

2022. 7. 10. 23:01· Koala - 7기/코딩테스트 준비 스터디

https://www.acmicpc.net/problem/4963 

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

 

문제 해석

1이 입력된 곳(=섬)이 8개의 방향으로 이어져 있으면, 하나의 섬으로 인정한다. 지도에 있는 섬의 총 개수를 출력하는 문제이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<queue>
using namespace std;
struct node{
    int y;
    int x;
};
int map[50][50];
int visited[50][50];
int w,h;
int direct[8][2]={-1,0,
                  1,0,
                  0,-1,
                  0,1,
                  -1,-1,
                  -1,1,
                  1,-1,
                  1,1};
void bfs(int yy, int xx)
{
    queue<node>q;
    q.push({yy,xx});
    visited[yy][xx]=1;
 
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
 
        for(int t=0;t<8;t++)
        {
            int dy= now.y + direct[t][0];
            int dx=now.x + direct[t][1];
 
            if(dy<0 || dx <0 || dy>=h || dx>=w) continue; //범위밖
            if(visited[dy][dx]==1) continue; //재방문 방지
            if(map[dy][dx]==0) continue; // 바다
 
            visited[dy][dx]=1;
            q.push({dy, dx});
        }
    }
}
int main()
{
    while(1)
    {
        int cnt=0;
        cin >> w >> h;
        if(w==0 & h==0) break;
 
        for(int y=0;y<h; y++)
        {
            for(int x=0; x<w; x++)
            {
                cin >> map[y][x];
            }
        }
 
        for(int y=0;y<h; y++)
        {
            for(int x=0; x<w; x++)
            {
                if(map[y][x]==1 && visited[y][x]==0)
                {
                    cnt++;
                    bfs(y,x);
                }
            }
        }
        cout << cnt << '\n';
 
        for(int y=0;y<50; y++)
        {
            for(int x=0;x<50;x++)
            {
                map[y][x]=0;
                visited[y][x]=0;
            }
        }
    }
    return 0;
}
Colored by Color Scripter
cs

문제 풀이

전역변수로는 섬의 높이와 넓이, 지도 배열, 방문 배열, 방향배열을 만들어 주었다. 그리고 방향의 좌표를 알려줄 구조체도 만들었다. 

main ()함수에서 while문으로 입력을 받고, bfs함수를 호출하고, 초기화 시켜준다. (0,0)이 입력되면 break하여 while문이 끝나게 해주었다.

bfs()함수에서는 1이 입력되어 있는, y좌표와 x좌표를 넘겨주었다. q에 좌표를 push하고, 방문에 1도 표시하였다. 그리고 섬이 더 연결되지 않을 때까지, while문을 도는데 이때, q에 아무것도 남지 않으면 멈추는 조건을 넣어 주었다. node now를 만든 후, q의 맨앞에 있는 값을 넣어준다. 그 다음 q를 pop()해주어 없앤다. 그 다음 8가지의 방향으로 dy, dx의 좌표를 구한다. 이 때, 조건은 재방문 하면 안될 것, 지도 범위 밖을 넘어가면 안될 것, 바다(=0)를 거치면 안될 것 이다. 마지막으로 q에 새로운 좌표값 {dy,dx}를 넣어주고 1이 없을 때 까지,반복한다. 

저작자표시

'Koala - 7기 > 코딩테스트 준비 스터디' 카테고리의 다른 글

[백준/JAVA] 1520번 내리막 길  (0) 2022.07.12
[백준/C++] 9657번 돌 게임 3  (0) 2022.07.12
[백준/Python] 1895번 필터  (0) 2022.07.10
[백준/Python] 15666번: N과 M (12)  (0) 2022.07.10
[백준/Python] 1107번 리모컨  (0) 2022.07.09
'Koala - 7기/코딩테스트 준비 스터디' 카테고리의 다른 글
  • [백준/JAVA] 1520번 내리막 길
  • [백준/C++] 9657번 돌 게임 3
  • [백준/Python] 1895번 필터
  • [백준/Python] 15666번: N과 M (12)
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1833) N
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (22) N
      • 코딩테스트 기초 스터디 (9) N
      • 코딩테스트 심화 스터디 (13) N

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • BFS
  • dp
  • dfs
  • 백준
  • BOJ
  • 파이썬
  • C++
  • 백트래킹

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[백준/c++] 4963번 섬의 개수
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.