[ BOJ / 파이썬 ] 4179 불!

/  제출 1  /

 

from collections import deque
import copy

r, c = map(int, input().split())
board = [list(input()) for _ in range(r)]

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
jihoonBoard = copy.deepcopy(board)
fireBoard = copy.deepcopy(board)
jihoonStart = []
fireStart = []
for x in range(r):
  for y in range(c):
    if board[x][y] == 'J':
      jihoonBoard[x][y] = 1
      fireBoard[x][y] = 0
      jihoonStart = [(x, y)]
    elif board[x][y] == 'F':
      jihoonBoard[x][y] = 0
      fireBoard[x][y] = 1
      fireStart = [(x, y)]
    elif board[x][y] == '.':
      fireBoard[x][y] = 0
      jihoonBoard[x][y] = 0
      
visited = [[False]*c for _ in range(r)]
visited[fireStart[0][0]][fireStart[0][1]] = True
q = deque(fireStart)

def bfs(board):
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != '#' and visited[nx][ny] == False :
        q.append((nx, ny))
        visited[nx][ny] = True
        board[nx][ny] += board[x][y] + 1
      
def jhbfs(board, fireBoard):
  while q:
    x, y = q.pop()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != '#' and visited[nx][ny] == False and board[x][y]<fireBoard[nx][ny]:
        q.append((nx, ny))
        visited[nx][ny] = True
        board[nx][ny] += board[x][y] + 1
      if nx < 0 or r <= nx or ny < 0 or c <= ny:
        return board[x][y]
  return 'IMPOSSIBLE'
      
bfs(fireBoard)
#for i in range(r):
#  print(fireBoard[i])
q = deque(jihoonStart)
visited = [[False]*c for _ in range(r)]
visited[jihoonStart[0][0]][jihoonStart[0][1]] = True
#print('reseult: ')
print(jhbfs(jihoonBoard, fireBoard))
#for i in range(r):
#  print(jihoonBoard[i])

첫 풀이.

바로 틀렸는데, 질문검색방에 다른 분이 올려주신 반례 두 케이스에 모두 같은 output으로 실패했다.

질문 작성자가 나와 같은 생각으로 풀이하신 것 같다.

 

 

/  제출 2  /

 

from collections import deque
import copy

r, c = map(int, input().split())
board = [list(input()) for _ in range(r)]

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
jihoonBoard = copy.deepcopy(board)
fireBoard = copy.deepcopy(board)
jihoonStart = []
fireStart = []
for x in range(r):
  for y in range(c):
    if board[x][y] == 'J':
      jihoonBoard[x][y] = 1
      fireBoard[x][y] = 0
      jihoonStart = [(x, y)]
    elif board[x][y] == 'F':
      jihoonBoard[x][y] = 0
      fireBoard[x][y] = 1
      fireStart.append((x, y))  # 요 부분 수정
    elif board[x][y] == '.':
      fireBoard[x][y] = 0
      jihoonBoard[x][y] = 0
      
visited = [[False]*c for _ in range(r)]
visited[fireStart[0][0]][fireStart[0][1]] = True
q = deque(fireStart)

def bfs(board):
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != '#' and visited[nx][ny] == False :
        q.append((nx, ny))
        visited[nx][ny] = True
        board[nx][ny] += board[x][y] + 1
      
def jhbfs(board, fireBoard):
  while q:
    x, y = q.pop()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != '#' and visited[nx][ny] == False:
        if fireBoard[nx][ny] == 0 or board[x][y]<fireBoard[nx][ny]:   # 요 부분 수정
          q.append((nx, ny))
          visited[nx][ny] = True
          board[nx][ny] += board[x][y] + 1
      if nx < 0 or r <= nx or ny < 0 or c <= ny:
        return board[x][y]
  return 'IMPOSSIBLE'
      
bfs(fireBoard)
#for i in range(r):
#  print(fireBoard[i])
q = deque(jihoonStart)
visited = [[False]*c for _ in range(r)]
visited[jihoonStart[0][0]][jihoonStart[0][1]] = True
#print('reseult: ')
print(jhbfs(jihoonBoard, fireBoard))
#for i in range(r):
#  print(jihoonBoard[i])

그래서 불이 2가지 나는 경우를 생각해 처음 불 시작위치를 하나로 지정하는게 아니라 여러 개를 큐에 넣는 식으로 바꾸고, fireboard가 0 상태로 남아 있는 경우를 고려해 또 수정했습니다.

 

 

그런데도 23 % 정도 뜨다가 틀렸습니다. 가 떠서 일단 후퇴합니다.

1시간이 지났기 때문에 다른 분들 풀이 보고 학습하는게 나을 것 같습니다. 

 

 

/  제출 3  /

from collections import deque
import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = [list(input().strip()) for _ in range(r)]

def bfs():
  while f_queue:
    x, y = f_queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < r and 0 <= ny < c:
        if not f_visited[nx][ny] and board[nx][ny] != '#':
          f_visited[nx][ny] = f_visited[x][y] + 1
          f_queue.append((nx, ny))

  while j_queue:
    x, y = j_queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0 <= nx < r and 0 <= ny < c:
        if not j_visited[nx][ny] and board[nx][ny] != '#':
          if not f_visited[nx][ny] or f_visited[nx][ny] > j_visited[x][y] + 1:
            j_visited[nx][ny] = j_visited[x][y] + 1
            j_queue.append((nx, ny))
      else:
        return j_visited[x][y] + 1
  return 'IMPOSSIBLE'
          

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
f_queue, j_queue = deque(), deque()
f_visited, j_visited = [[0] * c for _ in range(r)], [[0] * c for _ in range(r)]

for i in range(r):
  for j in range(c):
    if board[i][j] == 'F':
      f_queue.append((i, j))
    if board[i][j] == 'J':
      j_queue.append((i, j))

print(bfs())

 

정말 까다롭네요. 골드는 골드구나 싶었습니다. 

그래도 이렇게 어렵고 테스트케이스에 까다로운 걸 많이 접해봐야 실력이 늘 것 같습니다.