Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Python
- graph
- Math
- udemy
- JavaScript
- C
- 따라하며 배우는 C언어
- web
- server
- Algospot
- Algorithm
- String
- greedy
- 따배씨
- 정수론
- php
- BFS
- sorting
- BOJ
- 백준
- 종만북
- C언어
- 따라하면서 배우는 C언어
- 생활코딩
- DP
- 인프런
- Cleancode
- dfs
- programmers
- BASIC
Archives
- Today
- Total
몽상실현개발주의
[BOJ] 4963 / 섬의 개수 / Python 파이썬 본문

[BOJ] 4963 / 섬의 개수 / Python 파이썬
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
풀이
주어진 이차원 배열에서 상하좌우 그리고 대각선으로 이어진 그룹의 개수를 구하는 문제이다.
인접한 섬을 찾는 방법은 이차원 배열에서의 기본 탐색 방법을 사용하였고 (dy, dx)
Queue 를 사용한 BFS 로 경로를 저장하여 탐색하였다.
import sys
from collections import deque
input = sys.stdin.readline
def BFS(s_y, s_x):
global w, h
dx = [0, 0, 1, -1, -1, 1, -1, 1]
dy = [-1, 1, 0, 0, -1, -1, 1, 1]
dq = deque()
dq.append((s_y, s_x))
while dq:
y, x = dq.popleft()
for i in range(8):
Y = y + dy[i]
X = x + dx[i]
if 0 <= Y < h and 0 <= X < w and maps[Y][X]:
maps[Y][X] = 0
dq.append((Y, X))
while True:
w, h = map(int, input().split())
if not w or not h:
break
maps = [0] * h
for i in range(h):
maps[i] = list(map(int, input().split()))
res = 0
for y in range(h):
for x in range(w):
if maps[y][x]:
res += 1
maps[y][x] = 0
BFS(y, x)
print(res)
'Algorithm PS > BOJ' 카테고리의 다른 글
[BOJ] 2178 / 미로 탐색 / Python 파이썬 (0) | 2021.06.13 |
---|---|
[BOJ] 7576 / 토마토 / Python 파이썬 (0) | 2021.06.10 |
[BOJ] 2667 / 단지번호붙이기 / Python 파이썬 (0) | 2021.06.09 |
[BOJ] 9466 / 텀 프로젝트 / Python 파이썬 (0) | 2021.06.09 |
[BOJ] 2331 / 반복수열 / Python 파이썬 (0) | 2021.06.07 |