[BOJ] 16956 - 늑대와 양

사용 언어: Python3

문제

백준 16956

코드

내 풀이

R, C = map(int, input().split())
farm = [list(input()) for _ in range(R)]

# 반시계 방향
dx = [0,-1,0,1]
dy = [1,0,-1,0]

# 늑대 위치
wolfPos = [(i,j) for i in range(R) for j in range(C) if farm[i][j]=='W']
# 양 위치
sheepPos = [(i,j) for i in range(R) for j in range(C) if farm[i][j]=='S']

# 늑대를 반시계 방향으로 이동해 양과 만나면 0
def moveWolf(wolfPos, sheepPos):
  for zx,zy in zip(dx,dy):
    for pos in wolfPos:
      if (pos[0]+zx, pos[1]+zy) in sheepPos:
        return 0
  return 1

# output
ans = moveWolf(wolfPos, sheepPos)
print(ans)

if ans == 1:
  for i in range(R):
    for j in range(C):
      # 모든 .을 D로 대체
      if farm[i][j] == '.':
        farm[i][j] = 'D'
      print(farm[i][j], end='')
    print()

• 시간초과가 뜬다..
• 가장 핵심은 울타리를 최소로 사용할 필요가 없다는 것이다.
  • 따라서 늑대와 양이 바로 인접한 경우가 아니라면, 비어있는 모든 칸을 울타리(D)로 채워버리면 된다!

다른 풀이

# input
R, C = map(int, input().split())
farm = [list(input()) for _ in range(R)] # ✅ comprehension - 2차원 배열 입력받기

dx, dy = [0,-1,0,1], [1,0,-1,0] # ✅ 반시계 방향
ck = False # 늑대가 양을 만났는지 체크

for i in range(R):
  for j in range(C):
    if farm[i][j] == 'W':
      for k in range(4): # 사방에 S가 있는지 확인
        ii, jj = i+dx[k], j+dy[k]
        # 범위 넘어가면 예외처리
        if ii < 0 or ii == R or jj < 0 or jj == C:
          continue
        if farm[ii][jj] == 'S':
          ck = True
          break

# output
if ck == True:
  print(0)
else:
  print(1)
  for i in range(R):
    for j in range(C):
      if farm[i][j] not in 'SW': # ✅ S 혹은 W가 아니라면 
        farm[i][j] = 'D' # 울타리로 채워넣기
      print(farm[i][j], end='')
    print()

  # for row in farm:
  #   print(''.join(row))

• 늑대 위치와 양 위치를 따로 저장해놓을 필요 없이,
  farm 안에서 늑대를 만날때까지 순회하다가, 늑대를 만나면 늑대의 사방에서 양을 찾는 방법으로 해결할 수 있다.
• 범위 넘어가면 예외처리를 해주자!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기