๋ฌธ์ ์๊ฐ
๋ฌธ์ ๋งํฌ : https://boj.kr/3654
Tier : Diamond IV
Tag : 2-SAT
3์นธ์ ์ฐจ์งํ๋ L๋ชจ์์ ํผ์ฆ ์กฐ๊ฐ์ด ์๋ค. ์ค๊ฐ์ ๊ฒ์ ์์ด๋ฉฐ, ๋๋จธ์ง ๋ ์นธ์ ํ์ ์์ด๋ค.
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค N * M ํฌ๊ธฐ์ ํจํด์ด ์ฃผ์ด์ง๋๋ฐ,
์ฐ๋ฆฌ๋ ํด๋น ํผ์ฆ ์กฐ๊ฐ์ ์ ์ ํ ๋์์ ๋ ํจํด์ ์จ์ ํ ๋ง๋ค ์ ์๋์ง์ ๋ํ ์ฌ๋ถ๋ฅผ ํ์ธํด์ผ ํ๋ค.
์ด๋, ํผ์ฆ ์กฐ๊ฐ์ ํ์ ๊ฐ๋ฅํ์ง๋ง ๊ฒน์น ์ ์๋ค.
ํ์ด
1. ์ผ๋ฐ์ ์ธ ๊ท์น ์ฐพ๊ธฐ
ํจํด ๋ด์
-
๊ฒ์ ์ ์นธ์ ๊ธฐ์ค์ผ๋ก ๊ฐ๋ก์ ํ์ ์ ์นธ ํ๋, ์ธ๋ก์ ํ์ ์ ์นธ ํ๋๊ฐ ๋ถ์ด ์์ด์ผ L๋ชจ์์ด ์ฑ๋ฆฝํ๋ค. (a)
-
ํ์ ์ ์นธ์ ๊ธฐ์ค์ผ๋ก ์ธ์ ํ๋ ๊ฒ์ ์ ์นธ ์ค ํ๋์๋ง ํฌํจ๋์ด์ผ ํ๋ค. (b)
2. ์ ํจํ์ง ์์ ์ผ์ด์ค ์ฐพ๊ธฐ
ํจํด ๋ด์
-
ํ์ ์ ์นธ ๊ฐ์๊ฐ ๊ฒ์ ์ ์นธ ๊ฐ์์ ์ ํํ ๋ ๋ฐฐ์ฌ์ผ ํ๋ค. (c)
-
ํ์ ์ ์นธ๊ณผ ์ธ์ ํ ์นธ ์ค ๊ฒ์ ์ ์นธ์ด ์์ผ๋ฉด ์ ํจํ์ง ์์ ํจํด์ด๋ค. (d)
-
๊ฒ์ ์ ์นธ ๊ธฐ์ค์ผ๋ก ๊ฐ๊ฐ ๊ฐ๋ก, ์ธ๋ก์ ์ธ์ ํ ์นธ ์ค ํ๋๋ผ๋ ํ์ ์ ์นธ์ด ์์ผ๋ฉด ์ ํจํ์ง ์์ ํจํด์ด๋ค. (e)
3. ์์ ๊ท์น์ ํ ๋๋ก 2-SAT์ผ๋ก ๋ชจ๋ธ๋งํ๊ธฐ
์ด๋ป๊ฒ ํ๋ฉด ์ด ๊ท์น์ ๋ ผ๋ฆฌ์์ผ๋ก ๋ณํํ ์ ์์๊น?
ํน์ ๋ณ์ a, b, c, ...์ ๋ํด,
- (a v b) : a ๋๋ b๊ฐ true์ฌ์ผ ์ฑ๋ฆฝ
- (a v a) : a๊ฐ true์ฌ์ผ ์ฑ๋ฆฝ
- (!a v !b) ^ (!a v !c) ^ ... : a, b, c, ... ์ค 1๊ฐ ์ดํ๋ง true์ฌ์ผ ์ฑ๋ฆฝ
- (!a v b) ^ (a v !b) ^ (!a v c) ^ (a v !c) ^ ... : a, b, c, ... ๋ชจ๋ true์ด๊ฑฐ๋ false์ฌ์ผ ์ฑ๋ฆฝ
๋ฑ์ ๋ฐฉ์์ผ๋ก ๋ ผ๋ฆฌ์์ ๋ชจ๋ธ๋งํ ์ ์๋ค.
๋งน์ 1
์ด๋ฅผ ์ด์ฉํ์ฌ **๊ท์น (b)**์ ์ผ๋ถ๋ฅผ ์ถฉ์กฑํ์ง๋ง, ๊ฒ์ ์ ์นธ ์ ๋ถ ํฌํจ๋์ง ์๋ ๊ฒฝ์ฐ๋ ์๊ธธ ์ ์๋ค.
๊ทธ๋ฌ๋, ์ด ๋งน์ ์ ๊ท์น (c)๋ฅผ ํตํด ํด๊ฒฐํ ์ ์๋ค.
์๋ํ๋ฉด, ์ ๋ฐ ์ํฉ์ด ์ฌ ๊ฒฝ์ฐ ํ์ ์ ์นธ์ด ๋จ๊ฒ ๋๊ธฐ ๋๋ฌธ์ด๋ค.
๋งน์ 2
ํน์ ํ ๊ฒ์ ์ ์นธ์ ๋ํด, ์ฃผ๋ณ์ ํ์ ์ ์นธ์ด ๊ฐ๋ก ์ธ๋ก๋น ํ๋์ฉ๋ง ๋ถ์ด์ผ ํ๋ **์กฐ๊ฑด (a)**๋ ์ด๋ป๊ฒ ์ถฉ์กฑ์์ผ์ผ ํ ๊น?
์ด๋ฌํ ๋ฌธ์ ์ ์ ๋ค์๊ณผ ๊ฐ์ ๋ณ์ ์ค์ ์ผ๋ก ํด๊ฒฐํ ์ ์๋ค.
๊ฒ์ ์ ์นธ์ ์ธ์ ํ ๊ฐ๋ก ์นธ ์ค, ์ผ์ชฝ์ ์กด์ฌํ๋ ํ์ ์นธ์ false, ์ค๋ฅธ์ชฝ์ ์กด์ฌํ๋ ํ์ ์นธ์ true๋ก ๊ฐ์ฃผํ์ฌ ๋ณ์๋ฅผ ์ค์ ํ๋ค.
์ธ๋ก ์นธ์ ๊ฒฝ์ฐ์๋ ๋ง์ฐฌ๊ฐ์ง์ด๋ค.
ํน์ ๋ณ์๋ ๋ฌด์กฐ๊ฑด true ๋๋ false์ด๋ฏ๋ก, ๋ ผ๋ฆฌ์์ ์ด์ฉํ์ง ์๊ณ ๋ณ์ ์ค์ ๋ง์ผ๋ก ํด๊ฒฐํ ์ ์๋ค.
๋๋จธ์ง ๊ท์น (d), (e)์ ๊ฒฝ์ฐ ํน์ ์นธ์ ๊ฒน์น๋ ๋ณ์๋ฅผ ๋ชจ๋ ๋ชฐ์๋ฃ์ด (b)๋ฅผ ๊ตฌ์ฑํ ๋ ๊ฐ์ด ์ฒดํฌํ๋ฉด ๋๋ค.