백준 2589 보물섬 - 골드5 [파이썬]

https://www.acmicpc.net/problem/2589

2589번: 보물섬

 

요령

1. 냅다 2차원 배열의 처음부터 끝까지 탐색하면서 "L" 인 녀석을 찾는다.

2. 그녀석부터 시작해서 BFS를 탐색하는데, 다음 칸으로 넘어갈 때마다 time 을 1씩 더해주면서 간다.

3. 매번 time이 갱신될 때마다 전역변수에 있는 result와 비교해서 최대값으로 갱신해준다.

 

풀면서 배운점

1. 입력받을 때, 문자 사이에 빈 칸이 없을 때 2중 for문으로 직접 append 해주었는데, 한 줄로 쓸 수 있는 방법을 배웠다.

심지어 별로 속도 차이도 안남.

(2중 for문 했을 때 820ms, 한 줄로 입력받았을 때 816ms 였다)

mmap = [[] for i in range(R)]
for i in range(R):
	s = input().rstrip()
	for j in s:
    	mmap[i].append(j)

mmap = [list(input()) for i in range(R)]

 

풀이 코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split())
mmap = [[] for i in range(R)]
visited = [[False for i in range(C)] for i in range(R)]
result = 0
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for i in range(R):
    s = input().rstrip()
    for j in s:
        mmap[i].append(j)


def bfs():
    # print("\nbfs 시작")
    while queue:
        r, c, time = queue.popleft()
        # print(r, c, time)
        global result
        result = max(time, result)
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 > nr or nr >= R or 0 > nc or nc >= C or mmap[nr][nc] == "W" or tvisited[nr][nc] == True:
                continue
            queue.append((nr, nc, time+1))
            tvisited[nr][nc] = True


for r in range(R):
    for c in range(C):
        if mmap[r][c] == "L":
            queue = deque()
            queue.append((r, c, 0))
            tvisited = [m[:] for m in visited]
            tvisited[r][c] = True
            bfs()

print(result)