728x90
๋ฐ˜์‘ํ˜•

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

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] DFS/BFS level2 ํƒ€๊ฒŸ๋„˜๋ฒ„

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ์ฝ”๋”ฉ์—ฐ์Šต ์ค‘ level2์˜ DFS/BFS ์นดํ…Œ๊ณ ๋ฆฌ์˜ "ํƒ€๊ฒŸ๋„˜๋ฒ„" ๋ฌธ์ œ ํ’€์ด (๋ฌธ์ œ : ์•„๋ž˜ ๋งํฌ๐Ÿ‘‡๐Ÿ‘‡๐Ÿ‘‡) ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”. programmers.co.kr ๋ฌธ์ œํ’€์ด ์ฒ˜์Œ ์ ‘๊ทผ ๋ฐฉ์‹ (์ •ํ™•์„ฑ 75%, ํ…Œ์ผ€ 1,2๋ฒˆ ์‹œ๊ฐ„์ดˆ๊ณผ๋กœ ํ†ต๊ณผ ๋ชปํ•จ) ๋‚˜์˜ ๊ฒฝ์šฐ๋Š” ์ฒ˜์Œ ๋‘ ํ…Œ์ผ€์—์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋–ด๋‹ค. ์ ‘๊ทผ ๋ฐฉ์‹์€ ์ฃผ์–ด์ง„ numbers ๊ธธ์ด๋งŒํผ '+','-'๋กœ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ์— ๋Œ€ํ•ด์„œ ์ƒ์„ฑํ•ด์ฃผ๊ณ  ์ด๋ฅผ numbers์— ๋ถ™์—ฌ์ฃผ๋Š” ๊ฒƒ์ด์—ˆ๋‹ค. (itertools์˜ productํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉ) ์˜ˆ๋ฅผ ๋“ค์–ด, [4,1,2,1] ๊ฐ€ numbers๋กœ ์ฃผ์–ด์ง„๋‹ค๋ฉด, '+'์™€ '..

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

๐Ÿ’ป ๋ฐฑ์ค€ 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..

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

๐Ÿ’ป ๋ฐฑ์ค€ 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..

[๋ฐฑ์ค€ 2667] [dfs/bfs] ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ

๐Ÿ’ป ๋ฐฑ์ค€ 2667๋ฒˆ [๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ] ํ’€์ด) n = int(input()) map_ = [list(map(int,input())) for _ in range(n)] visited = [[0]*n for _ in range(n)] cnt_lst = [] cnt = 0 def dfs(x,y) : global cnt # 1. ๋ฐฉ๋ฌธํ•œ ๋…ธ๋“œ์ธ์ง€ ํ™•์ธ if not visited[x][y] : # ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ visited[x][y] = 1 if map_[x][y] == 0 : return # !!!!!!!!!!!!!!!!!!!!!!!!!!!์ด๊ฑฐ ํ•œ์ค„ ์•ˆํ•ด์„œ ํ‹€๋ ธ์—ˆ์Œ # 2. ์ธ์ ‘๋…ธ๋“œ ์ˆœํšŒ for [i,j] in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]] : if 0

[๋ฐฑ์ค€ 2178] [dfs/bfs] ๋ฏธ๋กœํƒ์ƒ‰

๐Ÿ’ป ๋ฐฑ์ค€ 2178๋ฒˆ [๋ฏธ๋กœํƒ์ƒ‰] ํ’€์ด) # ์ตœ์ข…์ œ์ถœ from collections import deque n,m = map(int,input().split()) miro = [list(map(int,input())) for _ in range(n)] visited = [[0]*m for _ in range(n)] dis = [[0]*m for _ in range(n)] q = deque([[0,0]]) visited[0][0] = 1 dis[0][0] = 1 while q : x,y = q.popleft() for [i,j] in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]] : if 0

[๋ฐฑ์ค€ 1260] [dfs/bfs] BFS์™€ DFS โ—

๐Ÿ’ป ๋ฐฑ์ค€ 1260๋ฒˆ [BFS์™€ DFS]1260๋ฒˆ: DFS์™€ BFS์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 ≤ M ≤ 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌwww.acmicpc.netํ’€์ด)# ์ตœ์ข…์ œ์ถœ from collections import deque n,m,v = map(int,input().split()) input_lst = sorted([list(map(int,input().split())) for _ in range(m)], key = lambda x : (x[0],x[1])) edge_lst = [[] for _ in range(n+1)] for v1,v2 i..

[๋ฐฑ์ค€ 2606] [dfs/bfs] ๋ฐ”์ด๋Ÿฌ์Šค

๐Ÿ’ป ๋ฐฑ์ค€ 2606๋ฒˆ [๋ฐ”์ด๋Ÿฌ์Šค] 2606๋ฒˆ: ๋ฐ”์ด๋Ÿฌ์Šค ์ฒซ์งธ ์ค„์—๋Š” ์ปดํ“จํ„ฐ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ปดํ“จํ„ฐ์˜ ์ˆ˜๋Š” 100 ์ดํ•˜์ด๊ณ  ๊ฐ ์ปดํ“จํ„ฐ์—๋Š” 1๋ฒˆ ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๋„คํŠธ์›Œํฌ ์ƒ์—์„œ ์ง์ ‘ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ปดํ“จํ„ฐ ์Œ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด www.acmicpc.net ํ’€์ด) def dfs(graph, v, visited) : # ๋…ธ๋“œ ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ visited[v] = True # ์ธ์ ‘๋…ธ๋“œ ์ˆœํšŒ for i in graph[v] : if visited[i] == False : dfs(graph, i, visited) n_com,n_pair = int(input()),int(input()) input_lst = [list(map(int,input().split())) for _ in range(n_pai..

[๋ฐฑ์ค€ 2331] [dfs] ๋ฐ˜๋ณต์ˆ˜์—ด

๐Ÿ’ป ๋ฐฑ์ค€ 2331๋ฒˆ [๋ฐ˜๋ณต์ˆ˜์—ด] 2331๋ฒˆ: ๋ฐ˜๋ณต์ˆ˜์—ด ์ฒซ์งธ ์ค„์— ๋ฐ˜๋ณต๋˜๋Š” ๋ถ€๋ถ„์„ ์ œ์™ธํ–ˆ์„ ๋•Œ, ์ˆ˜์—ด์— ๋‚จ๊ฒŒ ๋˜๋Š” ์ˆ˜๋“ค์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ํ’€์ด) ์ฒซ๋ฒˆ์งธ ์ œ์ถœ : ๋Ÿฐํƒ€์ž„์—๋Ÿฌ(ModuleNotFoundError) ๋œธ ์•Œ๊ณ ๋ณด๋‹ˆ ๋ฐฑ์ค€์—์„œ๋Š” numpy๋ฅผ ๋ชป ์“ฐ๊ฒŒ ํ•จ...;;^^ # ์ฒซ๋ฒˆ์งธ import numpy as np a,p = map(int,input().split()) visited = {} stack = [] def cal(a,p) : if a in visited : return stack.pop() else : visited[a] = 1 stack.append(a) return cal(np.sum([int(i)**p for i in str(a)]),p) dup_n = cal..

728x90
๋ฐ˜์‘ํ˜•