๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/3190)
<๋ฑ>
๋ฌธ์
'Dummy'๋ผ๋ ๋์ค ๊ฒ์์ด ์๋ค. ์ด ๊ฒ์์๋ ๋ฑ์ด ๋์์ ๊ธฐ์ด ๋ค๋๋๋ฐ, ์ฌ๊ณผ๋ฅผ ๋จน์ผ๋ฉด ๋ฑ ๊ธธ์ด๊ฐ ๋์ด๋๋ค. ๋ฑ์ด ์ด๋ฆฌ์ ๋ฆฌ ๊ธฐ์ด ๋ค๋๋ค๊ฐ ๋ฒฝ ๋๋ ์๊ธฐ ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด ๊ฒ์์ด ๋๋๋ค.
๊ฒ์์ NxN ์ ์ฌ๊ฐ ๋ณด๋ ์์์ ์งํ๋๊ณ , ๋ช๋ช ์นธ์๋ ์ฌ๊ณผ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋ณด๋์ ์ํ์ข์ฐ ๋์ ๋ฒฝ์ด ์๋ค. ๊ฒ์์ด ์์ํ ๋ ๋ฑ์ ๋งจ ์ ๋งจ ์ข์ธก์ ์์นํ๊ณ ๋ฑ์ ๊ธธ์ด๋ 1์ด๋ค. ๋ฑ์ ์ฒ์์ ์ค๋ฅธ์ชฝ์ ํฅํ๋ค.
๋ฑ์ ๋งค ์ด๋ง๋ค ์ด๋์ ํ๋๋ฐ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ ๋ฐ๋ฅธ๋ค.
๋จผ์ ๋ฑ์ ๋ชธ๊ธธ์ด๋ฅผ ๋๋ ค ๋จธ๋ฆฌ๋ฅผ ๋ค์์นธ์ ์์น์ํจ๋ค.
๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๊ทธ ์นธ์ ์๋ ์ฌ๊ณผ๊ฐ ์์ด์ง๊ณ ๊ผฌ๋ฆฌ๋ ์์ง์ด์ง ์๋๋ค.
๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๋ชธ๊ธธ์ด๋ฅผ ์ค์ฌ์ ๊ผฌ๋ฆฌ๊ฐ ์์นํ ์นธ์ ๋น์์ค๋ค. ์ฆ, ๋ชธ๊ธธ์ด๋ ๋ณํ์ง ์๋๋ค.
์ฌ๊ณผ์ ์์น์ ๋ฑ์ ์ด๋๊ฒฝ๋ก๊ฐ ์ฃผ์ด์ง ๋ ์ด ๊ฒ์์ด ๋ช ์ด์ ๋๋๋์ง ๊ณ์ฐํ๋ผ.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ณด๋์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๋ค. (2 ≤ N ≤ 100) ๋ค์ ์ค์ ์ฌ๊ณผ์ ๊ฐ์ K๊ฐ ์ฃผ์ด์ง๋ค. (0 ≤ K ≤ 100)
๋ค์ K๊ฐ์ ์ค์๋ ์ฌ๊ณผ์ ์์น๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ฒซ ๋ฒ์งธ ์ ์๋ ํ, ๋ ๋ฒ์งธ ์ ์๋ ์ด ์์น๋ฅผ ์๋ฏธํ๋ค. ์ฌ๊ณผ์ ์์น๋ ๋ชจ๋ ๋ค๋ฅด๋ฉฐ, ๋งจ ์ ๋งจ ์ข์ธก (1ํ 1์ด) ์๋ ์ฌ๊ณผ๊ฐ ์๋ค.
๋ค์ ์ค์๋ ๋ฑ์ ๋ฐฉํฅ ๋ณํ ํ์ L ์ด ์ฃผ์ด์ง๋ค. (1 ≤ L ≤ 100)
๋ค์ L๊ฐ์ ์ค์๋ ๋ฑ์ ๋ฐฉํฅ ๋ณํ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋๋ฐ, ์ ์ X์ ๋ฌธ์ C๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ. ๊ฒ์ ์์ ์๊ฐ์ผ๋ก๋ถํฐ X์ด๊ฐ ๋๋ ๋ค์ ์ผ์ชฝ(C๊ฐ 'L') ๋๋ ์ค๋ฅธ์ชฝ(C๊ฐ 'D')๋ก 90๋ ๋ฐฉํฅ์ ํ์ ์ํจ๋ค๋ ๋ป์ด๋ค. X๋ 10,000 ์ดํ์ ์์ ์ ์์ด๋ฉฐ, ๋ฐฉํฅ ์ ํ ์ ๋ณด๋ X๊ฐ ์ฆ๊ฐํ๋ ์์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๊ฒ์์ด ๋ช ์ด์ ๋๋๋์ง ์ถ๋ ฅํ๋ค.
๋ฌธ์ ํ์ด
- my solution
import sys
if __name__=='__main__':
N=int(input()) # ๋ณด๋ ํฌ๊ธฐ
k=int(input()) # ์ฌ๊ณผ ๊ฐ์
graph=[[0]*N for i in range(N)]
for i in range(k): # ์ฌ๊ณผ ์์น ํ์
x,y=map(int,sys.stdin.readline().split())
graph[x-1][y-1]=1
L=int(input()) # ๋ฑ์ ๋ฐฉํฅ ๋ณํ ํ์
info=[]
for i in range(L): # ๋ฑ์ ๋ฐฉํฅ ๋ณํ ์ ๋ณด
info.append(sys.stdin.readline().split())
now=[[0,0]] # ๋ฑ์ ์์น ๊ธฐ๋ก
D='R' # ๋ฐฉํฅ
snake=[[0]*N for i in range(N)] # ๋ฑ
snake[0][0]=1
time=0 # ์ด
while True:
if len(info)!=0: # x ์ด ๋๋ ๋ค ๋ฐฉํฅ ํ์
if time==int(info[0][0]):
temp=info.pop(0)
if temp[1]=='L': # ๋ฐฉํฅ ์ ํ
if D=='R':
D='U'
elif D=='L':
D='D'
elif D=='U':
D='L'
else:
D='R'
else:
if D=='R':
D='D'
elif D=='L':
D='U'
elif D=='U':
D='R'
else:
D='L'
time += 1
if D=='R': # ์ค๋ฅธ์ชฝ
temp=[now[-1][0], now[-1][1]+1]
elif D=='L': # ์ผ์ชฝ
temp=[now[-1][0], now[-1][1]-1]
elif D=='U': # ์
temp=[now[-1][0]-1, now[-1][1]]
else: # ์๋
temp=[now[-1][0]+1, now[-1][1]]
if temp[0] >= 0 and temp[0] < N and temp[1] >= 0 and temp[1] < N: # ๋ณด๋ ๋ฒ์ ์์ด๋ผ๋ฉด
if snake[temp[0]][temp[1]] == 1: # ์๊ธฐ ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด ๊ฒ์ ๋
break
snake[temp[0]][temp[1]] = 1 # ๋ฑ ๋จธ๋ฆฌ๋ฅผ ๋ค์ ์นธ์ ์์น
now.append(temp) # ๋ฑ ์์น ์ถ๊ฐ
if graph[now[-1][0]][now[-1][1]] != 1: # ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด ๋ชธ ๊ธธ์ด๋ฅผ ์ค์ฌ์ ๊ผฌ๋ฆฌ๊ฐ ์์นํ ์นธ์ ๋น์
temp = now.pop(0)
snake[temp[0]][temp[1]] = 0
else: # ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด ์ฌ๊ณผ๊ฐ ์์ด์ง๊ณ ๊ผฌ๋ฆฌ๋ ์์ง์ด์ง ์์
graph[now[-1][0]][now[-1][1]]=0
else: # ๋ฒฝ์ ๋ถ๋ชํ๋ฉด ๊ฒ์ ๋
break
print(time)
- ๋ณด๋ ํฌ๊ธฐ(N), ์ฌ๊ณผ ๊ฐ์(k), ์ฌ๊ณผ ์์น(graph), ๋ฐฉํฅ ๋ณํ ํ์(L), ๋ฐฉํฅ ๋ณํ ์ ๋ณด ์ ๋ ฅ(info)
- ๋ฑ์ ์์น ์ขํ ๊ธฐ๋ก(now), ๋ฐฉํฅ (D), ๋ฑ์ ์์น ๊ธฐ๋ก (snake), ์ด (time)
- ๋ฌดํ ๋ฃจํ
: ๋ฑ์ ๋ฐฉํฅ ๋ณํ ์ ๋ณด์ ์ฃผ์ด์ง ์ด์ time์ด ๊ฐ๋ค๋ฉด ๋ฐฉํฅ ์ ํ -> ์ค๋ฅธ์ชฝ, ์ผ์ชฝ, ์์ชฝ, ์๋์ชฝ์ธ ๊ฒฝ์ฐ L, D ์ผ ๋ ๋ฐฉํฅ์ด ๋ค ๋ค๋ฅด๋ฏ๋ก ๊ฒฝ์ฐ๋ฅผ ๋๋์ด ๋ฐฉํฅ ํ์
: 1์ด ์ฆ๊ฐ
: ๋ฐฉํฅ(D)์ ๋ฐ๋ผ ์ค๋ฅธ์ชฝ, ์ผ์ชฝ, ์, ์๋๋ก ์ด๋ํ ์ขํ ๊ตฌํ๊ธฐ
: ์ด๋ํ ์ขํ๊ฐ ๋ณด๋ ๋ฒ์ ์์ด๋ผ๋ฉด
-> ์๊ธฐ ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด(=snake ๋ฆฌ์คํธ์์ ์ด๋ํ ์ขํ์ ๊ฐ์ด ์ด๋ฏธ 1์ด๋ผ๋ฉด) ๊ฒ์ ๋
-> ์๊ธฐ ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ์ง ์์ผ๋ฉด snake ๋ฆฌ์คํธ์์ ์ด๋ํ ์ขํ์ ๊ฐ์ 1๋ก ์ ์ฅ ๋ฐ ๋ฑ์ ์์น ์ขํ ๊ธฐ๋ก(now)์ ์ถ๊ฐ
-> ์ด๋ํ ์์น์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด ๊ผฌ๋ฆฌ๊ฐ ์์นํ ์นธ์ ๋น์์ค ( now ๊ฐ pop, snake ๊ฐ 0์ผ๋ก ๊ต์ฒด)
-> ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด ์ฌ๊ณผ๊ฐ ์์ด์ง๊ณ ๊ผฌ๋ฆฌ๋ ๊ทธ๋๋ก
: ์ด๋ํ ์ขํ๊ฐ ๋ณด๋ ๋ฒ์ ๋ฐ์ด๋ผ๋ฉด
-> ๋ฒฝ์ ๋ถ๋ชํ๋ ๊ฒ์ด๋ฏ๋ก ๊ฒ์ ๋ - time ์ถ๋ ฅ
โ ์ฒ์์ ์ ํ๋ ธ๋๊ฐ?
๋ ๋ฒ์งธ ์กฐ๊ฑด์ ์ ๋๋ก ๊ตฌํํ์ง ์์๊ธฐ ๋๋ฌธ์ด๋ค. ๋ ๋ฒ์งธ ์กฐ๊ฑด์์ ๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๊ทธ ์นธ์ ์๋ ์ฌ๊ณผ๊ฐ ์์ด์ง๊ณ ๊ผฌ๋ฆฌ๋ ์์ง์ด์ง ์๋๋ค์์ ์ฌ๊ณผ๊ฐ ์์ด์ง๋ ๊ฒ์ ๊ตฌํํ์ง ์์๊ธฐ ๋๋ฌธ์ ํ๋ ธ๋ ๊ฒ์ด๋ค. ์ฌ๊ณผ๋ฅผ ํ๋ฒ ๋จน์๋ค๋ฉด graph์ ๊ทธ ๊ฐ์ 0์ผ๋ก ๋ฐ๊ฟ์ฃผ๋ ์ฝ๋๋ฅผ ํ ์ค ์ถ๊ฐํ๋๋ ํต๊ณผํ ์ ์์๋ค.
โ ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋๋ฐ ์ค๋ ๊ฑธ๋ฆฐ ์ด์ ๋?
์ฒ์์๋ ๋จ์ง ๋ฑ์ ๊ผฌ๋ฆฌ์ ๋จธ๋ฆฌ ์์น๋ง ๊ธฐ๋กํ์ฌ ๋ฑ์ ๋ชธํต์ด ์ด๋ ์์นํ๋์ง๋ฅผ ํ๋ณํ๋๋ฐ ์ด๋ ค์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์๋ค. ๊ทธ๋์ ์๊ฐํ ๊ฒ์ด ๋ฐฉ๋ฌธํ ๊ณณ์ ํ์ํ๋ ๊ฒ์ฒ๋ผ ๋ฑ์ ๋ชธํต์ ๋ฆฌ์คํธ์ ํ์ํ๊ธฐ๋ก ํ์๋ค. ๋ํ ๋ฑ์ ๋ฐฉํฅ์ ํ์ํ๋๋ฐ ๋ง์ ์กฐ๊ฑด๋ฌธ์ ์ฌ์ฉํ์ฌ ์ด๊ฒ ๋ง๋ ์ถ์๋ค ใ ใ
์๊ฐ๐ค
๋ฌธ์ ์์ ์ ์ํ๋ ์กฐ๊ฑด์ ๋น ํธ๋ฆฌ์ง ๋ง ๊ฒ ๐ฅ
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 2493_ํ (0) | 2022.03.28 |
---|---|
[Baekjoon] 1068_ํธ๋ฆฌ (0) | 2022.03.25 |
[Baekjoon] 7569_ํ ๋งํ (0) | 2022.03.22 |
[Baekjoon] 7576_ํ ๋งํ (0) | 2022.03.21 |
[Baekjoon] 10026_์ ๋ก์์ฝ (0) | 2022.03.20 |