hgk0404.tistory
Code After Work
hgk0404.tistory

공지사항

전체 방문자
오늘
어제
  • 전체 카테고리
    • [컴퓨터비전]
    • [Computer Science]
      • [컴퓨터네트워크]
      • [알고리즘]
      • [자료구조 in C]
      • [C & C++]
      • [이산수학]
      • [Math]
    • [머신러닝]
      • [Numpy, Pandas]
    • [Cloud]
      • [AWS]
      • [NCP]
      • [Kubernetes]
      • [Terraform]
    • [Dev]
      • [가상환경]
      • [Linux]
      • [Docker]
    • [Python]
    • [Coding Test]
      • [백준]
      • [프로그래머스]
      • [SQL]
    • [WEB]
    • [일상]
    • [엑셀]
    • [금융]

인기 글

최근 글

최근 댓글

250x250
hELLO · Designed By 정상우.
hgk0404.tistory

Code After Work

[백준] 4963: 섬의 개수
[Coding Test]/[백준]

[백준] 4963: 섬의 개수

2022. 7. 10. 16:41
728x90

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

 

import sys
sys.setrecursionlimit(10**4)
while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0:
        break
    graph = [  ]
    for i in range(h):
        graph.append(list(map(int, sys.stdin.readline().split())))
    visited = [ [0]*w for _ in range(h) ]
    dx = [ 0, 0, -1, 1, 1, 1, -1, -1 ]
    dy = [ -1, 1, 0, 0, 1, -1, -1, 1 ]
    count = 0
    def dfs(x, y):
        visited[x][y] = 1
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if graph[nx][ny] == 1 and not visited[nx][ny]:
                    dfs(nx, ny)
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1 and not visited[i][j]:
                dfs(i, j)
                count += 1
    print(count)

graph[h][w]입니다. w, h가 입력되지만, (w는 너비, h는 높이) w=5, h=4일 때

   w=0  1  2  3  4   (너비, width)
h=0  [1, 1, 1, 0, 0]
h=1  [1, 1, 0, 0, 0]
h=2  [0, 0, 0, 1, 1]
h=3  [0, 0, 0, 1, 1]

이렇게 되기 때문에 graph[h][w] h= 3, w= 4일때 가장 오른쪽 아래에 있는 1이 됩니다.

그래서 x자리에 h가 들어가고 y자리에 w가 들어갑니다. 우리가 관례적으로 x라는 단어가 첫 번째인자에 들어가고 y가 두 번째 자리에 들어가는 겁니다. 위치이지 의미는 없습니다.

행을 먼저 탐색하고 그 행속에서 열을 탐색해서 원하는 원소를 찾게됩니다. 행을 이루는 것이 h이고, 열을 이루는 것이 너비인 w입니다.

728x90
저작자표시 동일조건 (새창열림)

'[Coding Test] > [백준]' 카테고리의 다른 글

[백준] 3085: 사탕 게임  (0) 2022.07.16
[백준] 2309: 일곱 난쟁이  (0) 2022.07.16
[백준] 11724: 연결 요소의 개수  (0) 2022.07.08
[백준] 1929 파이썬(python) : 소수 구하기 - (에라토스테네스의 체)  (0) 2022.07.05
[백준] 11650: 좌표 정렬하기  (0) 2022.07.04
'[Coding Test]/[백준]' 카테고리의 다른 글
  • [백준] 3085: 사탕 게임
  • [백준] 2309: 일곱 난쟁이
  • [백준] 11724: 연결 요소의 개수
  • [백준] 1929 파이썬(python) : 소수 구하기 - (에라토스테네스의 체)
hgk0404.tistory
hgk0404.tistory
공부기록

티스토리툴바