๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/3184)
<์>
๋ฌธ์
๋ฏธํค์ ๋ท๋ง๋น์๋ ํน์ ์์ ์์ด ์๋ค. ๊ทธ๊ฐ ํน ์ ๋ ์ฌ์ด์ ๋ฐฐ๊ณ ํ ๋๋๋ ๋ง๋น์ ๋ค์ด์ ์์ ๊ณต๊ฒฉํ๋ค.
๋ง๋น์ ํ๊ณผ ์ด๋ก ์ด๋ฃจ์ด์ง ์ง์ฌ๊ฐํ ๋ชจ์์ด๋ค. ๊ธ์ '.' (์ )์ ๋น ํ๋๋ฅผ ์๋ฏธํ๋ฉฐ, ๊ธ์ '#'๋ ์ธํ๋ฆฌ๋ฅผ, 'o'๋ ์, 'v'๋ ๋๋๋ฅผ ์๋ฏธํ๋ค.
ํ ์นธ์์ ์ํ, ์์ง๋ง์ผ๋ก ์ด๋ํ๋ฉฐ ์ธํ๋ฆฌ๋ฅผ ์ง๋์ง ์๊ณ ๋ค๋ฅธ ์นธ์ผ๋ก ์ด๋ํ ์ ์๋ค๋ฉด, ๋ ์นธ์ ๊ฐ์ ์์ญ ์์ ์ํด ์๋ค๊ณ ํ๋ค. ๋ง๋น์์ "ํ์ถ"ํ ์ ์๋ ์นธ์ ์ด๋ค ์์ญ์๋ ์ํ์ง ์๋๋ค๊ณ ๊ฐ์ฃผํ๋ค.
๋คํํ ์ฐ๋ฆฌ์ ์์ ๋๋์๊ฒ ์ธ์์ ๊ฑธ ์ ์๊ณ ์์ญ ์์ ์์ ์๊ฐ ๋๋์ ์๋ณด๋ค ๋ง๋ค๋ฉด ์ด๊ธฐ๊ณ , ๋๋๋ฅผ ์ฐ๋ฆฌ์์ ์ซ์๋ธ๋ค. ๊ทธ๋ ์ง ์๋ค๋ฉด ๋๋๊ฐ ๊ทธ ์ง์ญ ์์ ๋ชจ๋ ์์ ๋จน๋๋ค.
๋งจ ์ฒ์ ๋ชจ๋ ์๊ณผ ๋๋๋ ๋ง๋น ์ ์์ญ์ ์กด์ฌํ๋ค.
์์นจ์ด ๋๋ฌํ์ ๋ ์ด์๋จ์ ์๊ณผ ๋๋์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ.
์ ๋ ฅ
์ฒซ ์ค์๋ ๋ ์ ์ R๊ณผ C๊ฐ ์ฃผ์ด์ง๋ฉฐ(3 ≤ R, C ≤ 250), ๊ฐ ์๋ ๋ง๋น์ ํ๊ณผ ์ด์ ์๋ฅผ ์๋ฏธํ๋ค.
๋ค์ R๊ฐ์ ์ค์ C๊ฐ์ ๊ธ์๋ฅผ ๊ฐ์ง๋ค. ์ด๋ค์ ๋ง๋น์ ๊ตฌ์กฐ(์ธํ๋ฆฌ, ์, ๋๋์ ์์น)๋ฅผ ์๋ฏธํ๋ค.
์ถ๋ ฅ
ํ๋์ ์ค์ ์์นจ๊น์ง ์ด์์๋ ์๊ณผ ๋๋์ ์๋ฅผ ์๋ฏธํ๋ ๋ ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
๋ฌธ์ ํ์ด
- my solution
import sys
from collections import deque
def survival(arr, visited, start, result):
queue=deque([start])
sheep=0;wolf=0
if arr[start[0]][start[1]]=='v': # ๋๋
wolf+=1
elif arr[start[0]][start[1]]=='o': # ์
sheep+=1
dx=[-1,1,0,0] # ์ํ์ข์ฐ
dy=[0,0,-1,1]
while queue:
temp=queue.popleft()
for i in range(4):
x=temp[0]+dx[i]
y=temp[1]+dy[i]
if 0<=x<len(arr) and 0<=y<len(arr[0]) and visited[x][y]==0:
if arr[x][y]!="#":
queue.append([x,y])
visited[x][y]=1
if arr[x][y]=='v':
wolf+=1
elif arr[x][y]=='o':
sheep+=1
else:
visited[x][y]=1
if sheep>wolf:
result[0]+=sheep
else:
result[1]+=wolf
def main():
r,c=map(int, input().split()) # ํ, ์ด
arr=[]
for i in range(r):
arr.append(list(sys.stdin.readline().strip()))
visited=[[0]*c for i in range(r)] # ๋ฐฉ๋ฌธ ์ฌ๋ถ
result=[0,0] # ์, ๋๋ ์
for i in range(r):
for j in range(c):
if arr[i][j]!='#' and visited[i][j]==0: # ์ธํ๋ฆฌ๊ฐ ์๋๊ณ ์์ง ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด
visited[i][j]=1 # ๋ฐฉ๋ฌธ
survival(arr, visited, [i,j], result)
print(str(result[0])+" "+ str(result[1]))
if __name__=='__main__':
main()
- survival ( arr, ๋ฐฉ๋ฌธ ์ฌ๋ถ, ์์ ์ขํ, ๊ฒฐ๊ณผ )
: sheep, wolf = ๊ฐ์ ์์ญ์์ ์ด์๋จ์ ์๊ณผ ๋๋์ ์
: queue๊ฐ ๋น ๋๊น์ง ๋ฐ๋ณต -> ์ ์ผ ์ฒ์ ๊ฐ์ pop ํ์ฌ ์ํ์ข์ฐ๋ฅผ ํ์ -> ๋ฒ์ ์์ด๋ฉฐ ์์ง ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด -> ์ธํ๋ฆฌ๊ฐ ์๋๋ผ๋ฉด queue์ ์ถ๊ฐ ๋ฐ ๋ฐฉ๋ฌธ, ์์ด๋ ๋๋์ธ ๊ฒฝ์ฐ wolf, sheep์ +1 but ์ธํ๋ฆฌ๋ผ๋ฉด ๋ฐฉ๋ฌธ๋ง ํ์
: ๊ฐ์ ์์ญ ํ์์ ๋๋ธ ํ ์์ด ๋๋๋ณด๋ค ๋ง๋ค๋ฉด result [0]์ ์์ ์ ๋ํด์ฃผ๊ณ ๋๋๊ฐ ๋ง๊ฑฐ๋ ๊ฐ๋ค๋ฉด result [1]์ ๋๋ ์ ๋ํด์ค - main
: ํ r, ์ด c ์ ๋ ฅ
: arr ์ ๋ ฅ
: visited = ๋ฐฉ๋ฌธ ์ฌ๋ถ
: result = [์, ๋๋]
: arr ์ ์ฒด๋ฅผ ํ์ํ์ฌ ์ธํ๋ฆฌ๊ฐ ์๋๊ณ ์์ง ๋ฐฉ๋ฌธํ์ง ์์๋ค๋ฉด ๋ฐฉ๋ฌธ ํ ํจ์ ํธ์ถ
: result ์ถ๋ ฅ
์๊ฐ๐ค
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 15649, 15650, 15651, 15652 N๊ณผ M (0) | 2022.08.03 |
---|---|
[Baekjoon] 2564_๊ฒฝ๋น์ (0) | 2022.06.10 |
[Baekjoon] 14500_ํ ํธ๋ก๋ฏธ๋ ธ (0) | 2022.05.31 |
[Baekjoon] 21608_์์ด ์ด๋ฑํ๊ต (0) | 2022.05.27 |
[Baekjoon] 16236_์๊ธฐ ์์ด (0) | 2022.05.26 |