๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/14503)
<๋ก๋ด ์ฒญ์๊ธฐ>
๋ฌธ์
๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์ฃผ์ด์ก์ ๋, ์ฒญ์ํ๋ ์์ญ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์ฅ์๋ N×M ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, 1 ×1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ฐ๊ฐ์ ์นธ์ ๋ฒฝ ๋๋ ๋น์นธ์ด๋ค. ์ฒญ์๊ธฐ๋ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ด ์์ผ๋ฉฐ, ์ด ๋ฐฉํฅ์ ๋, ์, ๋จ, ๋ถ์ค ํ๋์ด๋ค. ์ง๋์ ๋ถ์ชฝ์์๋ถํฐ r๋ฒ์งธ, ์์ชฝ์์๋ถํฐ c๋ฒ์งธ๋ก ์์นํ ์นธ์ (r, c)๋ก ๋ํ๋ผ ์ ์๋ค.
๋ก๋ด ์ฒญ์๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ด ์๋ํ๋ค.
1. ํ์ฌ ์์น๋ฅผ ์ฒญ์ํ๋ค.
2. ํ์ฌ ์์น์์ ๋ค์์ ๋ฐ๋ณตํ๋ฉด์ ์ธ์ ํ ์นธ์ ํ์ํ๋ค.
a. ํ์ฌ ์์น์ ๋ฐ๋ก ์ผ์ชฝ์ ์์ง ์ฒญ์ํ์ง ์์ ๋น ๊ณต๊ฐ์ด ์กด์ฌํ๋ค๋ฉด, ์ผ์ชฝ ๋ฐฉํฅ์ผ๋ก ํ์ ํ ๋ค์ ํ ์นธ์ ์ ์งํ๊ณ 1๋ฒ์ผ๋ก ๋์๊ฐ๋ค. ๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ, ์ผ์ชฝ ๋ฐฉํฅ์ผ๋ก ํ์ ํ๋ค. ์ด๋, ์ผ์ชฝ์ ํ์ฌ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ ๊ธฐ์ค์ผ๋ก ํ๋ค.
b. 1๋ฒ์ผ๋ก ๋์๊ฐ๊ฑฐ๋ ํ์งํ์ง ์๊ณ 2a๋ฒ ๋จ๊ณ๊ฐ ์ฐ์์ผ๋ก ๋ค ๋ฒ ์คํ๋์์ ๊ฒฝ์ฐ, ๋ฐ๋ก ๋ค์ชฝ์ด ๋ฒฝ์ด๋ผ๋ฉด ์๋์ ๋ฉ์ถ๋ค. ๊ทธ๋ ์ง ์๋ค๋ฉด ํ ์นธ ํ์งํ๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ธ๋ก ํฌ๊ธฐ N๊ณผ ๊ฐ๋ก ํฌ๊ธฐ M์ด ์ฃผ์ด์ง๋ค. (3 ≤ N, M ≤ 50)
๋์งธ ์ค์ ๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์นธ์ ์ขํ (r, c)์ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ d๊ฐ ์ฃผ์ด์ง๋ค. d๊ฐ 0์ธ ๊ฒฝ์ฐ์๋ ๋ถ์ชฝ์, 1์ธ ๊ฒฝ์ฐ์๋ ๋์ชฝ์, 2์ธ ๊ฒฝ์ฐ์๋ ๋จ์ชฝ์, 3์ธ ๊ฒฝ์ฐ์๋ ์์ชฝ์ ๋ฐ๋ผ๋ณด๊ณ ์๋ ๊ฒ์ด๋ค.
์ ์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ์ฅ์์ ์ํ๊ฐ ๋ถ์ชฝ๋ถํฐ ๋จ์ชฝ ์์๋๋ก, ๊ฐ ์ค์ ์์ชฝ๋ถํฐ ๋์ชฝ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๋น์นธ์ 0, ๋ฒฝ์ 1๋ก ์ฃผ์ด์ง๋ค. ์ง๋์ ์ฒซ ํ, ๋ง์ง๋ง ํ, ์ฒซ ์ด, ๋ง์ง๋ง ์ด์ ์๋ ๋ชจ๋ ์นธ์ ๋ฒฝ์ด๋ค.
๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์นธ์ ์ํ๋ ํญ์ ๋น์นธ์ด๋ค.
์ถ๋ ฅ
๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์ฒญ์ํ๋ ์นธ์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
๋ฌธ์ ํ์ด
- my solution (Python)
import sys
if __name__=='__main__':
n,m=map(int,sys.stdin.readline().split()) # ์ธ๋ก, ๊ฐ๋ก
r,c,d=map(int,sys.stdin.readline().split()) # ์ขํ, ๋ฐฉํฅ
arr=[]
visited=[[0]*m for i in range(n)] # ๋ฐฉ๋ฌธ ์ฌ๋ถ
for i in range(n):
temp=list(map(int,sys.stdin.readline().split()))
arr.append(temp)
location=[r,c,d]
visited[r][c] = 1
answer=1
cnt=0 # 2a๋ฒ ์คํ count
while location:
if location[2]==0: # ๋ถ -> ์ผ์ชฝ
x=location[0]
y=location[1]-1
elif location[2]==1: # ๋ -> ์ผ์ชฝ
x=location[0]-1
y=location[1]
elif location[2]==2: # ๋จ -> ์ผ์ชฝ
x=location[0]
y=location[1]+1
else: # ์ -> ์ผ์ชฝ
x=location[0]+1
y=location[1]
if 0<=x<n and 0<=y<m:
if visited[x][y]==0 and arr[x][y]==0: # ๋น ๊ณต๊ฐ + ๋ฐฉ๋ฌธ x
visited[x][y] = 1
cnt=0
answer += 1
location[2]-=1 # ์ผ์ชฝ ๋ฐฉํฅ์ผ๋ก ํ์
if location[2]<0:
location[2]=3
location=[x,y,location[2]]
else:
location[2]-=1 # ์ผ์ชฝ ๋ฐฉํฅ์ผ๋ก ํ์
cnt+=1
if location[2]<0:
location[2]=3
if cnt==4: # 2a ์ฐ์์ผ๋ก 4๋ฒ ์คํ -> ๋ฐ๋ก ๋ค
if location[2] == 0: # ๋ถ
x = location[0] +1
y = location[1]
elif location[2] == 1: # ๋
x = location[0]
y = location[1]-1
elif location[2] == 2: # ๋จ
x = location[0] -1
y = location[1]
else: # ์
x = location[0]
y = location[1]+1
if 0<=x<n and 0<=y<m:
if arr[x][y]==1: # ๋ฒฝ
location=[]
else: # ๋ฒฝ x -> ํ์ง
location=[x,y,location[2]]
cnt=0
print(answer)
ํ์ฌ ๋ฐฉํฅ์์ ์ผ์ชฝ์ผ๋ก ํ์ ํ๋ฉด ์ด๋ ๋ฐฉํฅ์ธ์ง ๊ตฌํ๋ ๊ฒ์ด ์ ค ์ค์ํ๋ค.
- ์ธ๋ก, ๊ฐ๋ก ํฌ๊ธฐ ์ ๋ ฅ
- ์ขํ, ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ ์ ๋ ฅ
- arr = ์ฅ์์ ์ํ
visited = ๋ฐฉ๋ฌธ ์ฌ๋ถ
location = ํ์ฌ ์์น, ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ
answer = ์ฒญ์ํ๋ ์นธ์ ๊ฐ์
cnt = 2a๋ฒ ๋จ๊ณ๊ฐ ์ฐ์์ผ๋ก ์คํ๋๋ ์ - ์๋์ด ๋ฉ์ถ ๋๊น์ง ๋ฐ๋ณต
-> ์ผ์ชฝ์ผ๋ก ์ด๋ํ ์์น๊ฐ ๋น ๊ณต๊ฐ์ด๋ฉฐ ์์ง ๋ฐฉ๋ฌธํ์ง ์์์ผ๋ฉด ๋ฐฉ๋ฌธ ๋ฐ cnt ์ด๊ธฐํ, ์ฒญ์ํ๋ ์นธ +1, ์ผ์ชฝ ๋ฐฉํฅ์ผ๋ก ํ์ / ์ฒญ์ํ์ง ์์ ๋น ๊ณต๊ฐ์ด ์๋๋ผ๋ฉด ์ผ์ชฝ ๋ฐฉํฅ์ผ๋ก ํ์ ๋ง
-> 2a๋ฒ ๋จ๊ณ๊ฐ ์ฐ์์ผ๋ก 4๋ฒ ์คํ๋์์ ๊ฒฝ์ฐ ํ์ฌ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์์ ๋ค์ชฝ ์์น๋ฅผ ๊ตฌํ ํ ๊ทธ ์์น๊ฐ ๋ฒฝ์ด๋ผ๋ฉด ์๋ ๋ฉ์ถค/ ๋ฒฝ์ด ์๋๋ผ๋ฉด ํ์ง - answer ์ถ๋ ฅ
โ ์ด๋ ๋ถ๋ถ์ ๋์ณค๋๊ฐ?
ํ ์นธ ํ์งํ ๋ ๋ฒฝ์ด ์๋๋ฉด ๋ฐฉ๋ฌธํ๋ ๊ณณ์ด๋ผ๋ ํ์งํ ์ ์๋ค๋ ๊ฒ์ ๋์ณค๋ค. ์ฒ์์ ๊ตฌํํ ๋ ๋ค๊ฐ ๋ฒฝ์ด๊ฑฐ๋ ๋ฐฉ๋ฌธํ๋ ๊ณณ์ด๋ฉด ํ์ง ๋ชปํ๊ฒ ํ๊ธฐ ๋๋ฌธ์ ์ ๋๋ก ๋ ๋ต์ด ๋์ค์ง ์์๋ ๊ฒ์ด๋ค.
์๊ฐ๐ค
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 23288_์ฃผ์ฌ์ ๊ตด๋ฆฌ๊ธฐ 2 (0) | 2022.05.11 |
---|---|
[Baekjoon] 14499_์ฃผ์ฌ์ ๊ตด๋ฆฌ๊ธฐ (0) | 2022.05.09 |
[Baekjoon] 2638_์น์ฆ (0) | 2022.04.27 |
[Baekjoon] 1303_์ ์ - ์ ํฌ (0) | 2022.04.26 |
[Baekjoon] 1747_์์&ํฐ๋ฆฐ๋๋กฌ (0) | 2022.04.25 |