[백준|파이썬] 4963: 섬의 개수 (실버2)

2023. 4. 11. 12:55·Problem Solving/백준
반응형
문제

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

 

4963번: 섬의 개수

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

www.acmicpc.net

 

 

🐍파이썬
import sys
from collections import deque
#상하좌우, 대각선 모두 방문하기 위해 좌표설정
dy = [-1, 1, 0, 0, -1, 1, -1, 1]
dx = [0, 0, -1, 1, 1, 1, -1, -1]
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx >= h or ny >= w or nx < 0 or ny < 0: #배열의 범위를 넘어서는 경우 건너뛰기
continue
if island[nx][ny] == 0: #바다인 경우 건너뛰기
continue
if island[nx][ny] == 1: #육지인 경우
island[nx][ny] = 0 #중복 피하기 위해 0으로 덮어씌워 방문처리
queue.append((nx, ny)) #다음 육지를 찾기 위해 큐에 현재의 좌표 저장
while True:
w, h = map(int, sys.stdin.readline().split())
if w == 0 and h == 0:
break
island = []
for i in range(h):
island.append(list(map(int, sys.stdin.readline().split())))
visited = [[0] * w for _ in range(h)]
answer = 0
for i in range(h):
for j in range(w):
if island[i][j] == 1: #육지인 경우
bfs(i, j) #bfs를 이용해 연결된 모든 육지를 발견
answer += 1 #이어진 육지를 하나씩 발견할 때마다 answer+1
print(answer)

 

반응형

'Problem Solving > 백준' 카테고리의 다른 글

[백준|파이썬] 13700: 완전 범죄 (실버1)  (0) 2023.04.11
[백준|파이썬] 21736: 헌내기는 친구가 필요해(DFS/BFS 풀이) (실버2)  (0) 2023.04.11
[백준|파이썬] 2667: 단지번호붙이기(DFS/BFS 풀이) (실버1)  (0) 2023.04.11
[백준|파이썬] 11724: 연결 요소의 개수 (실버2)  (0) 2023.04.10
[백준|파이썬] 25418: 정수 a를 k로 만들기 (실버3)  (0) 2023.04.10
[백준|파이썬] 6186: Best Grass (실버5)  (0) 2023.04.10
'Problem Solving/백준' 카테고리의 다른 글
  • [백준|파이썬] 21736: 헌내기는 친구가 필요해(DFS/BFS 풀이) (실버2)
  • [백준|파이썬] 2667: 단지번호붙이기(DFS/BFS 풀이) (실버1)
  • [백준|파이썬] 11724: 연결 요소의 개수 (실버2)
  • [백준|파이썬] 25418: 정수 a를 k로 만들기 (실버3)
청량리 물냉면
청량리 물냉면
프로그래밍 공부를 하고 있습니다. 공부 내용 정리 겸 정보 공유를 목적으로 합니다.
    반응형
  • 청량리 물냉면
    노력중인 블로그
    청량리 물냉면
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 프로그래밍
        • Programming
        • C | C++
        • Java
        • Python
      • 웹 프로그래밍
        • HTML | CSS
        • JavaScript | TypeScript
        • React
        • Vue.js
        • Next.js
        • Spring & Spring Boot
        • JSP & Servlet
        • DB
      • 웹 프로젝트
        • 웹 프로젝트
        • 🥨스낵몰
        • 👨‍👨‍👧‍👧소셜 가계부
        • 🌜꿈 일기장
        • 🔮포트폴리오 사이트
        • 🏃‍♂️팀 프로젝트: 일정관리 프로그램
        • 📈팀 프로젝트: AI기반 주식 분석 플랫폼
        • 😺Just Meow It: 고양이의 조언
      • 앱 프로그래밍
        • Flutter
        • Kotlin
      • Problem Solving
        • 백준
        • 프로그래머스
        • SWEA
      • Computer Science
        • 알고리즘
        • 컴퓨터 네트워크
        • 이산수학
      • Developer
        • 후기
        • 자료정리
        • 취업 | 취준
        • 웹개발 교육 프로그램
        • TIL
  • 블로그 메뉴

    • 홈
    • Github
  • 공지사항

    • 프로그래밍 공부 중😊
  • 인기 글

  • 태그

    spring boot
    컴퓨터네트워크
    ZeroCho
    클론 프로젝트
    타입스크립트
    React
    블로그 제작
    SWEA
    프로그래머스
    자바스크립트
    Next.js
    프로젝트
    백준
    포트폴리오
    강의내용정리
    리액트
    Til
    파이썬
    bfs
    구현
    자바
    웹사이트
    d3
    Jiraynor Programming
    공식문서
    mysql
    AWS
    뉴렉처
    알고리즘
    플러터
  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
청량리 물냉면
[백준|파이썬] 4963: 섬의 개수 (실버2)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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