HelloMinchan
처음처럼
HelloMinchan
LinkedIn
전체 방문자
오늘
어제
  • 분류 전체보기 (306)
    • Backend (4)
      • NestJS (1)
      • Express (1)
      • Spring (2)
    • Infrastructure (1)
      • AWS (1)
    • Frontend (1)
      • Next.js (1)
    • Language & Runtime (4)
      • Java (2)
      • Node.js (2)
    • Computer Science (8)
      • Computer Networks (3)
      • Operating Systems (4)
      • OOP (1)
    • 독서 (4)
      • 데이터 중심 애플리케이션 설계 (3)
      • 객체지향의 사실과 오해 (1)
    • 회고 (4)
      • Project (2)
      • Career (2)
    • Deprecated (280)

채널

  • GitHub
  • LinkedIn

최근 글

태그

  • 알고스팟
  • 프로그래머스
  • programmers
  • 개발자
  • 백준
  • 코딩
  • 프로그래밍
  • back-end
  • Algospot
  • Baekjoon Online Judge
  • 프로그래머스C++
  • 알고스팟Python
  • 데이터베이스
  • 백엔드
  • front-end
  • 백준Go
  • Database
  • 백준C++
  • 프로그래머스Python
  • 백준Python

최근 댓글

인기 글

hELLO
HelloMinchan

처음처럼

[Baekjoon Online Judge] 백준 4963번 섬의 개수(Python)
Deprecated

[Baekjoon Online Judge] 백준 4963번 섬의 개수(Python)

2020. 3. 29. 00:12

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 4963번 섬의 개수

(Python)

(글쓴날 : 2020.03.29)

 


* Baekjoon Online Judge, 백준 4963번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

백준 4963번 섬의 개수


1) 문제

문제 링크 : https://www.acmicpc.net/problem/4963

 

4963번: 섬의 개수

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.  두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는

www.acmicpc.net


2) 풀이 과정

1과 0이 저장되어 있는 2차원 배열이 주어지고 1을 땅, 0을 바다라 가정했을 때 땅들이 가로 세로 또는 대각선으로 연결되어 있는 섬의 개수를 출력하는 문제입니다.

 

저의 경우, BFS를 적용해 문제를 해결했으며, 2차원 배열을 완전 탐색하다 1이 발견되면 BFS를 통해 상하좌우와 대각선으로 연결되어 있는 땅들을 판별했습니다.

그 후, 총 BFS() 함수가 호출된 횟수로 섬의 개수를 구하여 문제를 해결했습니다.


3) 코드

 

* Python 코드

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
import sys, queue
input = sys.stdin.readline
 
 
def BFS(i, j):
    global w, h, MAP, visit, dx, dy, island
    island += 1
 
    q = queue.Queue()
    q.put((i, j))
 
    while q.qsize():
        x, y = q.get()
 
        if visit[x][y] == False:
            visit[x][y] = True
            for way in range(8):
                ii, jj = x + dx[way], y + dy[way]
 
                if ii < 0 or ii > h - 1 or jj < 0 or jj > w - 1:
                    continue
 
                if MAP[ii][jj] == 1:
                    q.put((ii, jj))
 
 
while True:
    w, h = map(int, input().split())
    if not w + h:
        exit()
    
    MAP = [list(map(int, input().split())) for _ in range(h)]
    visit = [[False] * w for _ in range(h)]
    dx, dy = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
    island = 0
 
    for i in range(h):
        for j in range(w):
            if MAP[i][j] == 1 and visit[i][j] == False:
                BFS(i, j)
    
    print(island)

 

저작자표시 비영리 변경금지 (새창열림)

'Deprecated' 카테고리의 다른 글

[Baekjoon Online Judge] 백준 1697번 숨바꼭질(Python)  (0) 2020.03.30
[Baekjoon Online Judge] 백준 15663번 N과 M (9)(Python)  (0) 2020.03.30
[Baekjoon Online Judge] 백준 15649번 N과 M (1)(Python)  (0) 2020.03.28
[Baekjoon Online Judge] 백준 2667번 단지번호붙이기(Python)  (0) 2020.03.28
[Baekjoon Online Judge] 백준 15686번 치킨 배달(Python)  (0) 2020.03.28
    'Deprecated' 카테고리의 다른 글
    • [Baekjoon Online Judge] 백준 1697번 숨바꼭질(Python)
    • [Baekjoon Online Judge] 백준 15663번 N과 M (9)(Python)
    • [Baekjoon Online Judge] 백준 15649번 N과 M (1)(Python)
    • [Baekjoon Online Judge] 백준 2667번 단지번호붙이기(Python)
    HelloMinchan
    HelloMinchan
    Though you should not fear failure, You should do your very best to avoid it.

    티스토리툴바