[BaekJoon] 1012 ์œ ๊ธฐ๋† ๋ฐฐ์ถ”

2022. 4. 12. 13:16ยท๐Ÿ’ฏ CodingTest/BaekJoon

โ–ถ ๋ฌธ์ œ :

๋”๋ณด๊ธฐ

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

[์ถœ์ฒ˜ : https://www.acmicpc.net/problem/1012]

import sys

t = int(input())
sys.setrecursionlimit(10**6)

def dfs(a, b):
    if a < 0 or a >= m or b < 0 or b >= n:
        return

    if graph[a][b] == 0:
        return

    graph[a][b] = 0
    dfs(a - 1, b)
    dfs(a, b - 1)
    dfs(a + 1, b)
    dfs(a, b + 1) 

for _ in range(t):
    m, n, k = map(int, input().split())

    graph = [[0 for _ in range(n)]for _ in range(m)]

    for _ in range(k):
        a, b = map(int, input().split())
        graph[a][b] = 1
    
    result = 0
    for a in range(m):
        for b in range(n):
            if graph[a][b] == 1:
                dfs(a,b)
                result += 1

    print(result)

 

โ–ถ ๋ฌธ์ œํ’€์ด 

 

1. dfs() ์„ ์–ธ => ๋ฐฐ์—ด์˜ ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜๊ฑฐ๋‚˜ ํ•ด๋‹น ์นธ์˜ ๊ฐ’์ด 0์ด๋ฉด ๋ฐ˜ํ™˜ ์•„๋‹Œ ๊ฒฝ์šฐ์—” ํ•ด๋‹น ์นธ๊ณผ ์ธ์ ‘ํ•˜๋ฉด์„œ 1์„ ๊ฐ€์ง„ ์นธ์„ 0์œผ๋กœ ๋ณ€ํ™˜

2. graph๋ฐ์ดํ„ฐ๋ฅผ ์ˆœํšŒํ•˜๋ฉฐ 1๊ฐ’์„ ๊ฐ€์ง„ ์นธ์„ ์ฐพ์•„ ํ•ด๋‹น ์นธ๊ณผ ์ธ์ ‘ํ•œ 1๋“ค์„ 0์œผ๋กœ ๋ณ€ํ™˜

3. ํƒ์ƒ‰ ์ข…๋ฃŒ์‹œ 1์„ ๊ฐ€์ง„ ๊ตฐ์ง‘์„ 0์œผ๋กœ ๋ณ€ํ™˜ํ•  ๋•Œ์˜ ํšŸ์ˆ˜๋ฅผ ์„ผ result ๊ฐ’์„ ์ถœ๋ ฅ

 

'๐Ÿ’ฏ CodingTest > BaekJoon' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[BaekJoon] 1107 ๋ฆฌ๋ชจ์ปจ  (0) 2022.04.14
[BaekJoon] 1074๋ฒˆ Z  (0) 2022.04.13
[BaekJoon] 1003 ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜  (0) 2022.04.12
[BaekJoon] 18111 ๋งˆ์ธํฌ๋ž˜ํ”„ํŠธ  (0) 2022.04.11
[BaekJoon] 15829 Hashing  (0) 2022.04.11
'๐Ÿ’ฏ CodingTest/BaekJoon' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [BaekJoon] 1107 ๋ฆฌ๋ชจ์ปจ
  • [BaekJoon] 1074๋ฒˆ Z
  • [BaekJoon] 1003 ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜
  • [BaekJoon] 18111 ๋งˆ์ธํฌ๋ž˜ํ”„ํŠธ
S.Honey
S.Honey
  • S.Honey
    Algo ์“ฐ์ž
    S.Honey
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (123)
      • ํšŒ๊ณ  (0)
        • ์ทจ์—… ํ›„ ํšŒ๊ณ  (0)
      • ๐Ÿƒ Frontend Road-Map (2)
        • ๐Ÿšฉ Summary (1)
        • ๐Ÿ“š Road-Map Contents (1)
        • ๐ŸŸง HTML (0)
        • ๐ŸŸฆ CSS (0)
        • ๐ŸŸจ Javascript (0)
        • โฌœ React (0)
        • ๐ŸŸช Redux (0)
      • Backend (0)
        • QueryDSL (0)
      • ๐Ÿ’ป Programming Language (54)
        • C# (51)
        • Flutter-Dart (3)
        • Java (0)
      • ๐Ÿ“š Computer Science (4)
        • Algorithms (4)
        • Database (0)
        • Network (0)
        • Operating System(OS) (0)
      • ๐Ÿ’ฏ CodingTest (60)
        • BaekJoon (22)
        • Programmers (34)
        • CodeTree (4)
      • โœ’๏ธ Design Pattern (1)
      • ๐Ÿฑ Etc (2)
        • Jenkins Plugin ์ œ์ž‘๊ธฐ (1)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ๋งํฌ

    • ๊ณต์ง€์‚ฌํ•ญ

      • ๐Ÿ“– ๊ณต๋ถ€ ์ฐธ๊ณ  ๊ต์žฌ ๋ฐ ์ž๋ฃŒ
    • ์ธ๊ธฐ ๊ธ€

    • ํƒœ๊ทธ

      ํŒŒ์ด์ฌ
      ๋ฐฑ์ค€
      ์Šคํ„ฐ๋””
      ๊ตฌํ˜„
      ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
      ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰
      JavaScript
      ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ
      sort
      ์‹œ๋ฎฌ๋ ˆ์ด์…˜
      c#
      ์ฝ”๋“œํŠธ๋ฆฌ
      BFS
      ์ฝ”๋”ฉํ…Œ์ŠคํŠธ
      JS
      Java
      ๋ฌธ์ž์—ด ํŒŒ์‹ฑ
      Flutter
      BAEKJOON
      DP
      ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ
      ์•Œ๊ณ ๋ฆฌ์ฆ˜
      ์ด์ง„ํƒ์ƒ‰
      ์“ฐ์…จ์ž–์•„
      DART
      ์‚ผ์„ฑsw์—ญํ…Œ
      Algorithm
      ์นด์นด์˜ค
      programmers
      ์ž๋ฃŒ๊ตฌ์กฐ
    • ์ตœ๊ทผ ๋Œ“๊ธ€

    • ์ตœ๊ทผ ๊ธ€

    • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.1
    S.Honey
    [BaekJoon] 1012 ์œ ๊ธฐ๋† ๋ฐฐ์ถ”
    ์ƒ๋‹จ์œผ๋กœ

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”