๋ฐฑ์ค€ & ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค/DFS & BFS

[๋ฐฑ์ค€ 1012] [dfs/bfs] ์œ ๊ธฐ๋† ๋ฐฐ์ถ”

_cactus 2021. 4. 24. 01:08
๋ฐ˜์‘ํ˜•

๐Ÿ’ป ๋ฐฑ์ค€ 1012๋ฒˆ [์œ ๊ธฐ๋† ๋ฐฐ์ถ”]

 

1012๋ฒˆ: ์œ ๊ธฐ๋† ๋ฐฐ์ถ”

์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— 

www.acmicpc.net

ํ’€์ด)

import sys
sys.setrecursionlimit(100000000)

T = int(input())
cnt_lst = []
for t in range(T) :
    m,n,k = map(int,input().split())
    cab = [list(map(int,input().split())) for _ in range(k)]

    map_ = [[0]*m for _ in range(n)]
    for i,j in cab : 
        map_[j][i] = 1
    visited = [[0]*m for _ in range(n)]
    def dfs(x,y,visited) :
        # 1. ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ์ธ์ง€ ํ™•์ธ
        if not visited[x][y] :
            # ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ
            visited[x][y] = 1
            if map_[x][y] == 0 : return False
            # 2. ์ธ์ ‘๋…ธ๋“œ ์ˆœํšŒ
            for [i,j] in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]] :
                if 0 <= i <= n-1 and 0 <= j <= m-1 :
                    if map_[i][j] == 1 and not visited[i][j]: 
                        dfs(i,j,visited)
                    elif map_[i][j] == 0 :
                        visited[i][j] = 1   

        return True

    cnt = 0 
    for i in range(n) :
        for j in range(m) :
            if not visited[i][j] : 
                bool_ = dfs(i,j,visited) 
                if bool_ : cnt+=1
    cnt_lst.append(cnt)
print(*cnt_lst,sep='\n')

 

๋ฉ”๋ชจ๋ฆฌ ์‹œ๊ฐ„ ์–ธ์–ด ์ฝ”๋“œ๊ธธ์ด
32148KB 404ms Python 3 1004B

 

๊ณผ์ •)

์ฒ˜์Œ ์ œ์ถœํ–ˆ์„ ๋•Œ ๋Ÿฐํƒ€์ž„์—๋Ÿฌ(recursion error)๊ฐ€ ๋ฐœ์ƒํ•˜์—ฌ

๋งจ ์œ„์— ๋‘์ค„์„ ์ถ”๊ฐ€ํ•ด์ฃผ์—ˆ๋‹ค

import sys
sys.setrecursionlimit(100000000)
728x90
๋ฐ˜์‘ํ˜•