내 인생 이대로 ㅈ될 수 없다

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

내 풀이

from collections import deque
import sys

input = sys.stdin.readline

def solution():
    n,m = map(int,input().split())
    graph=[list(input().strip()) for _ in range(n)]
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    def bfs(x,y):
        visit = [[0]* m for _ in range(n)]
        visit[x][y]=1
        q = deque([(x,y)])
        
        
        
        while q:
            x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0>nx or nx>=n or 0>ny or m<=ny or graph[nx][ny]=='W' or visit[nx][ny]  :
                    continue
                
                visit[nx][ny] = visit[x][y] + 1             
                q.append((nx,ny))
        
        return visit[x][y]-1
    max_time=0  
    for i in range(n):
        for j in range(m):
            if graph[i][j]=='L':
                if 0<=i-1 and i+1<n:
                    if graph[i-1][j]=='L' and graph[i+1][j]=='L':
                        continue
                if 0<=j-1 and j+1<m:
                    if graph[i][j-1]=='L'and graph[i][j+1]=='L':
                        continue
                max_time=max(bfs(i,j),max_time)
    print(max_time)
                
solution()

문제 자체는 진짜 평이했는데 그놈의 시간초과가 나를 괴롭혔다.

당연히 pypy로 풀면 해결되지만 코딩테스트에서는 pypy를 지원하지 않는 경우가 많아서 꼭 파이썬으로 풀고 싶었다.

조건을 조금 더 생각해보니, 그래프에서 양 옆이 모두 육지인 경우는 절대 최대값일 수가 없었다.

가령

LLW

LWW

LLL

이런 그래프가 있다하면

그래프에서 (0,2)인 지점은 절대 최대값일 수가 없다 왜?

내 옆에 땅을 거쳐가면 반드시 현재 위치보다 더 긴시간이 걸릴테니까

이런 문제의 핵심은 적어도 파이썬으로 풀때는, 숨겨진 조건을 찾는것인거 같다.

다른사람의 풀이

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
bomool = []
land = []
for i in range(N):
    temp = list(map(str, input()))
    for j in range(len(temp)):
        if temp[j] == 'L':
            land.append((i, j))
    bomool.append(temp)

dr = [-1, 0, 1, 0]  # 행 상 우 하 좌
dc = [0, 1, 0, -1]  # 열 상 우 하 좌


def bfs(r, c):
    queue = deque([[r, c, 0]])
    visited[r][c] = True
    while queue:
        r, c, distance = queue.popleft()

        for i in range(4):

            nr = r + dr[i]
            nc = c + dc[i]

            if nr < 0 or nr >= N or nc < 0 or nc >= M or visited[nr][nc] or bomool[nr][nc] == 'W':
                continue

            visited[nr][nc] = True
            queue.append([nr, nc, distance + 1])

    return distance


max_ = 0
for i in range(len(land)):
    visited = [[False] * M for _ in range(N)]
    distance = bfs(land[i][0], land[i][1])
    if max_ < distance:
        max_ = distance

print(max_)

https://ji-gwang.tistory.com/m/406