โ›น๏ธ ๋ผ์ดํ”„/2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ)

โ›น๏ธ ๋ผ์ดํ”„/2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ)

[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.23(์ˆ˜) - 1์ฃผ์ฐจ ๊ฐœ์ธ ๊ฒฐ๊ณผ

BFS์™€ DFS๋ฅผ ๊ฐœ๋…๊ณผ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ด„์œผ๋กœ์จ ๋‘˜์˜ ์ฐจ์ด์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์ž‘๋ฐฉ์‹์— ๋Œ€ํ•ด ํ™•์‹คํ•˜๊ฒŒ ์•„๋Š” ๊ณ„๊ธฐ๊ฐ€ ๋˜์—ˆ๋‹ค. 1. ์ด์›ƒ ๋…ธ๋“œ ์ฐพ๊ธฐ (๊ทธ๋ž˜ํ”„ ๊ธฐ๋ณธ) def main(): n, m = map(int, input().split()) node = list(input().split()) node_dict = dict() for i in range(n): node_dict[node[i]] = [] for i in range(m): srt, dst = input().split() if dst not in node_dict[srt]: node_dict[srt].append(dst) find_node = input() print(len(node_dict[find_node..

โ›น๏ธ ๋ผ์ดํ”„/2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ)

[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.23(์ˆ˜) - 1์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ

๋ชฉํ‘œ : BFS์™€ DFS๋ฅผ ๊ฐœ๋…๊ณผ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ณธ๋‹ค. ์‹ค์Šต์€ ์ด 3๋ฌธ์ œ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—… ์‹œ๊ฐ„์ด ์ง„ํ–‰๋˜์—ˆ๋˜ ์‹ค์Šต ๋ฌธ์ œ์ด๋‹ค. 1. ์ด์›ƒ ๋…ธ๋“œ ์ฐพ๊ธฐ (๊ทธ๋ž˜ํ”„ ๊ธฐ๋ณธ) ์ž…๋ ฅ ๊ฐ’์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฃผ์–ด์ง„๋‹ค. 4 4 # N M AA BB CC DD # ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ N ๊ฐœ AA CC # ๊ฐ„์„  ์ •๋ณด M ๊ฐœ BB DD AA BB BB AA AA # ์งˆ์˜ ๋…ธ๋“œ 2. BFS (๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰) ์ž…๋ ฅ ๊ฐ’์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฃผ์–ด์ง„๋‹ค. 12 11 # N M A B C D E F G H I J K L # ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ N ๊ฐœ A B # ๊ฐ„์„  ์ •๋ณด M ๊ฐœ A C A D B E B F D G D H E I E J G K G L A # ์งˆ์˜ ๋…ธ๋“œ 3. DFS (๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰) - ์œ„ ๊ทธ๋ž˜ํ”„์™€ ๋™์ผ 4..

kodo_o
'โ›น๏ธ ๋ผ์ดํ”„/2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ)' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก (2 Page)