๐ algorithm/boj105 BOJ 1916 - ์ต์๋น์ฉ ๊ตฌํ๊ธฐ ๋ฌธ์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง - 1916๋ฒ ํ์ด ๊ณผ์ ํ ์ ์ ์ผ๋ก๋ถํฐ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ๊ฒฝ๋ก ์ ๋ณด๋ฅผ ์ฌ์ฉํด ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค. ์ต์ ์ ๊ฒฝ์ฐ V = 1000์ด๊ณ E = 100,000 ์ด๋ฏ๋ก O(ElgV) ์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ์ ์ฌ์ฉํด์ ๋ต์ ๊ตฌํ ์ ์์ต๋๋ค. ์ฝ๋ import sys import heapq N = int(input()) M = int(input()) adj = [[] for _ in range(1001)] for _ in range(M): frm, to, cost = list(map(int, sys.stdin.readline().split())) adj[frm].append([to, cost]) start, goal = list(map(int, sys... 2021. 6. 7. BOJ 15684 - ์ฌ๋ค๋ฆฌ ์กฐ์ ๋ฌธ์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง - 15684๋ฒ ํ์ด ๊ณผ์ DFS ์ ๋ฐฑํธ๋ํน ์ ํ์ฉํ ์ต์ ํ๊ฐ ํ์ํ ํ์ ๋ฌธ์ ์ ๋๋ค. ์ด๋ ์ฌ๋ค๋ฆฌ์ ์์น๋ฅผ ๊ฒ์ฌํ๋ ๊ณผ์ ์์ ์ธ๋ฑ์ค ๋ฒ์์ ๋ํ ๊ณ ๋ ค๋ฅผ ์ํด์ฃผ๊ธฐ ์ํด board ์์ชฝ์ padding ์ ์ถ๊ฐํ์ต๋๋ค. ์ด๋ ๊ฒ ์ํ๋ฉด ์์ชฝ ์ฌ๋ค๋ฆฌ ์์น ์ธ๋ฑ์ค๊ฐ board ๋ฅผ ๋ฒ์ด๋๋์ง์ ๋ํ ์กฐ๊ฑด๋ฌธ์ ์ถ๊ฐํด์ค์ ์ฝ๋๊ฐ ๋ณต์กํด์ง๋๋ค. ์ฌ๋ค๋ฆฌ๋ฅผ 2์ฐจ์ ๋ฐฐ์ด๋ก ํํํ์ผ๋ฏ๋ก ๊ฐ ์์์ ์์ ํ๊ณ ๋ด๋ ค์ฌ๋๋ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ์์ ๋ง๋๋ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํด์ค์ผ ํฉ๋๋ค. ์ฃผ์ํ ์ ์ ์ํ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ์ ๊ฒฝ์ฐ์๋ ๋ฐ๋ก ํ์นธ ๋ฐ์ผ๋ก ์ ์ง์์ผ์ค์ผํฉ๋๋ค. (์๊ทธ๋ฌ๋ฉด ๋ฌดํ ๋ฃจํ์ ๋น ์ง๋๋ค.) DFS ๋ฅผ ์ํํ๋ ๊ณผ์ ์์ ๋ง์ฝ ๋ง์กฑํ๋ ์กฐํฉ์ ์ฐพ์์ ๊ฒฝ์ฐ์๋ ์ดํ ํ์์ ์ํํ์ง ์๊ณ ๋ฐ๋ก True ๋ฅผ ๋ฐํํ.. 2021. 6. 7. BOJ 1781 - ์ปต๋ผ๋ฉด ๋ฌธ์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง - 1781๋ฒ ํ์ด ๊ณผ์ ๋ง๊ฐ์ผ์ ๊ณ ๋ คํ์ฌ ๊ฐ์ฅ ๋ง์ ์ปต๋ผ๋ฉด์ ์ป์ ์ ์๋ ๋ฐฉ๋ฒ์ ์ฐพ๋ ๊ทธ๋ฆฌ๋ ๋ฌธ์ ์ ๋๋ค. ๋ฐ๋๋ผ์ธ์ ๋ง์ง๋ง ๋ ๋ถํฐ ์ํ๋ฅผ ํ๋ฉด์ ํด๋นํ๋ ๋ ์ด์์ ๋ ์ง์ ๋ํด์ ๊ฐ์ฅ ๋ง์ ์ปต๋ผ๋ฉด์ ์ป์ ์ ์๋ ๊ฒ์ ์ ํํ๋ฉด ๋ฉ๋๋ค. ์ด๋ฅผ ์ํด ์ฐ์ ์์ ํ ๋ฅผ ๋ ๊ฐ ์ฌ์ฉํด์ ํ๋๋ ๋ฐ๋๋ผ์ธ์ ๋ด๋ฆผ์ฐจ์์ผ๋ก, ๋ค๋ฅธ ํ๋๋ ์ปต๋ผ๋ฉด์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ฌ ์ฌ์ฉํฉ๋๋ค. ์ฝ๋ import sys import heapq N = int(input()) questions = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] def init_queue(): pq = [] for deadline, cups in question.. 2021. 6. 7. BOJ 6118 - ์จ๋ฐ๊ผญ์ง ๋ฌธ์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง - 6118๋ฒ ํ์ด ๊ณผ์ ์์ ์ ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ๊ฑฐ๋ฆฌ ์ค ๊ฐ์ฅ ๊ธด ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฌธ์ ์ ๋๋ค. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ์ ํ์ฉํ์ฌ ํ ์ ์ ์ผ๋ก๋ถํฐ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ ๋ค์, ๊ฐ์ฅ ๊ฑฐ๋ฆฌ๊ฐ ๋จผ ์ ์ ์ ์ฐพ์์ฃผ๋ฉด ๋ฉ๋๋ค. ์ด๋ ๊ตฌํ์ ํธ์๋ฅผ ์ํด์ dist ๋ฐฐ์ด์ ๊ฑฐ๋ฆฌ๊ฐ๊ณผ ์ ์ ๋ฒํธ์์ผ๋ก ์ ๋ ฌํ์ฌ ๋ต์ ๊ตฌํ์ต๋๋ค. ์ฝ๋ import sys import heapq INF = sys.maxsize N, M = list(map(int, sys.stdin.readline().split())) adj = [[] for _ in range(N+1)] for _ in range(M): frm, to = list(map(int, sys.stdin.readline().split(.. 2021. 6. 7. BOJ 2331 - ๋ฐ๋ณต์์ด ๋ฌธ์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง - 2331๋ฒ ํ์ด ๊ณผ์ ๊ท์น์ ๋ฐ๋ผ ์์ฑ๋๋ ์ซ์๋ค์ ๋ชจ๋ ํ์ํ๋ฉฐ ์ต์ข ์ ์ผ๋ก ๋ฐ๋ณต๋๋ ์์ด์ ์ ์ธํ ๋๋จธ์ง ์ซ์๋ค์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋๋ค. ์ด๋ฅผ ์ํด DFS ํ์์ ์ํํ๋ฉฐ ๊ฐ ์ซ์๋ค์ ์ฒ์ ๋ฐฉ๋ฌธ, ๋๋ฒ์งธ ๋ฐฉ๋ฌธ, ์ธ๋ฒ์งธ ๋ฐฉ๋ฌธ ์ด๋ ๊ฒ ์ธ ์ข ๋ฅ๋ก ๊ตฌ๋ถํด์ค๋๋ค. ์ฒซ๋ฒ์งธ ๋ฐฉ๋ฌธ์ ๊ฒฝ์ฐ๋ ๋ฌธ์ ๊ฐ ์์ง๋ง ๋๋ฒ์งธ ๋ฐฉ๋ฌธํ์๋๋ ํด๋น ์ซ์๊ฐ ์ค๋ณต๋์ด ๋ํ๋๋ค๋ ์๋ฏธ์ด๋ฏ๋ก ๋ฐฉ๋ฌธํ์๋ฅผ ์ฆ๊ธฐ์ํจ ํ ๋ค์ ํ์์ ์ํํฉ๋๋ค. ์ด๋ ๊ฐ์ฅ ์ฒ์ ์ธ๋ฒ์งธ ๋ฐฉ๋ฌธ๋๋ ์ซ์๊ฐ ๋ํ๋๋ ๊ฒฝ์ฐ ์ดํ์ ์ซ์๋ค์ ๋๋ค์ ๊ฒน์น๊ฒ ๋๋ฏ๋ก ํ์์ ๊ณ์ ์ํํ ํ์์์ด ๋ฐ๋ก ์ข ๋ฃํด์ฃผ๋ฉด ๋ฉ๋๋ค. ์ฝ๋ import sys sys.setrecursionlimit(10**6) A, P = list(map(int, sys.stdin... 2021. 6. 7. BOJ 4889 - ์์ ์ ์ธ ๋ฌธ์์ด ๋ฌธ์ ๋ฐฑ์ค ์จ๋ผ์ธ ์ ์ง - 4889๋ฒ ํ์ด ๊ณผ์ ์ฌ๋ ๊ดํธ์ ๋ซ๋ ๊ดํธ๋ฅผ ์ ์ ํ ๋ณํํ์ฌ ์ง์ด ๋ง๋๋ก ํ๋ ๋ฐฉ๋ฒ์ ์ฐพ๋ ๋ฌธ์ ์ ๋๋ค. ๊ดํธ ์ง ๋ง์ถ๊ธฐ ๋ฌธ์ ์ ์ ์ฌํ ์ปจ์ ์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์ต๋๋ค. ์ฐ์ ์ฌ๋ ๊ดํธ({)์ ๊ฒฝ์ฐ ํด๋น ๊ดํธ๊ฐ ์์ ์ ์ธ์ง๋ ์ด ๊ดํธ๋ง ๋ด์๋ ์ ์ ์์ต๋๋ค. (์ดํ์ ๋์ค๋ ๊ดํธ์ ์ํฅ์ ๋ฐ์) ๋์ ์ ๋ซ๋ ๊ดํธ(})์ ๊ฒฝ์ฐ ์ด์ ์ ์ฌ๋ ๊ดํธ๊ฐ ์กด์ฌํด์ผ๋ง ์์ ์ ์ธ ๋ฌธ์์ด์ ๋ง๋ค ์ ์์ต๋๋ค. ๋ง์ฝ ๋ซ๋ ๊ดํธ๊ฐ ๋์๋๋ฐ ์ฌ๋ ๊ดํธ๊ฐ ์กด์ฌํ์ง ์์ ๊ฒฝ์ฐ ์ ์ผํ ๋ฐฉ๋ฒ์ ํด๋น ๊ดํจ๋ฅผ ์ฌ๋ ๊ดํธ๋ก ๋ฐ๊พธ๋ ๊ฒ ๋ฟ์ ๋๋ค. ์ด๋ฃฐ ์ํด ์คํ ์ ํ์ฉํด์ ๊ดํธ ์ข ๋ฅ์ ๋ฐ๋ผ push, pop ์ ์ํํ๊ณ ์ต์ข ์ ์ผ๋ก ๋จ๋ ์ฌ๋ ๊ดํธ์ ๊ฐ์ / 2 ๊ฐ ํ์ํ ๋ซ๋ ๊ดํธ์ ๊ฐ์์ ๋๋ค. ์ฝ๋ impo.. 2021. 6. 7. ์ด์ 1 2 3 4 5 6 7 ยทยทยท 18 ๋ค์