๋ฌธ์
https://www.acmicpc.net/problem/2589
๋ฐฑ์ค ๋ฌธ์ ์ง - ๋ํ์ ๊ธฐ๋ณธ๋ฐ
ํ์ด
์ฌ์ค ๋ณด๋ฌผ์ด๊ณ ๋๋ฐ์ด๊ณ , ์ด ๋ฌธ์ ์ ํต์ฌ์ "์ก์ง-์ก์ง ๊ฐ์ ๊ฑฐ๋ฆฌ์ค ๊ฐ์ฅ ์ต๋๊ฐ"์ ๊ตฌํ๋๊ฒ์ด๋ค.
๋ณด๋ฌผ์ฌ ์ง๋์์ L์ ์ก์ง, W๋ ๋ฐ๋ค๋ฅผ ๋ํ๋ธ๋ค.
- ์ก์ง๋ ๋ชจ๋ ๋ถ์ด์๋๊ฒ์ด ์๋ ๋ช๊ฐ์ ์ฌ์ผ๋ก ์ด๋ฃจ์ด์ ธ์๋ ํํ๋ค.
- ๊ฐ์ฅ ๋จผ ๊ฑฐ๋ฆฌ๋ฅผ D๋ผ๊ณ ํ์๋, ์ด๋ L์ด ์์์ /๋์ ์ธ์ง ๋ถ๋ถ๋ช ํ๋ค.
๋ฐ๋ผ์ L์ ๋ฐ๊ฒฌํ ๋๋ง๋ค bfs๋ฅผ ์คํํด์ค์ผ ํ๋ค.
์ ์ฒด ์ฝ๋
# ๋ฌธ์ ์ง - ๋ํ์ ๊ธฐ๋ณธ๋ฐ
# ๋ฌธ์ : https://www.acmicpc.net/problem/2589
# ๋ฉ๋ชจ๋ฆฌ: 34072KB / ์๊ฐ: 4264ms
from sys import stdin
from collections import deque
input = stdin.readline
def bfs(x, y):
global ret
queue = deque([(x, y, 0)])
visited = [[False] * n for _ in range(m)]
visited[x][y] = True
while queue:
cx, cy, dis = queue.popleft()
ret = max(ret, dis)
for nx, ny in ((cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)):
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
if not visited[nx][ny] and MAP[nx][ny] == "L":
visited[nx][ny] = True
queue.append((nx, ny, dis + 1))
m, n = map(int, input().split())
MAP = [input().rstrip() for _ in range(m)]
ret = 0
for i in range(m):
for j in range(n):
if MAP[i][j] == "L":
bfs(i, j)
print(ret)
๋ชจ๋ L์ ๋ํด์ ์คํํ๊ธฐ๋๋ฌธ์ ์คํ์๊ฐ์ด ์ด๋ง์ด๋งํ๋ค.
๋ค๋ฅธํ์ด๋ฅผ ์ฐพ์๋ณด๋ ๋ด ์คํ์๊ฐ์ 1/10๋ ์๋๋ ์ผ์ด์ค๊ฐ ๋ง์๋ค...;;
(๊ทธ๋ฆฌ๊ณ ๋์ฒ๋ผ L์ ๋ฐ๊ฒฌํ ๋๋ง๋ค bfs๋ฅผ ์คํํ๋ค๊ฐ ์๊ฐ์ด๊ณผ๊ฐ ๋จ๋ ๊ฒฝ์ฐ๋ ์์๋ค.)
์๋ก์ด ํ์ด์ ๋ฐฉ์์ ์ด๋ฌํ๋ค.
๋ง์ฝ, ํด๋น L์ ์ํ or ์ข์ฐ์ L์ด ์กด์ฌํ๋ค๋ฉด?
ํ์ฌ์ L์ ์ค๊ฐ์ ๋ ๋ชจ์์์ด๋ฏ๋ก ์ต๋จ๊ฑฐ๋ฆฌ์ ์์์ ์ด ๋ ์ ์๋ค. => pass!
์๋๋ ๊ณต๊ฐ๋ ํ์ด ์ค ํ๋๋ค. ์คํ์๊ฐ์ 384ms!
(์ฌ์ค ๋ ๋น ๋ฅธ ํ์ด๋ ์์์ผ๋ ๊ฐ๋
์ฑ์ด ๋จ์ด์ ธ์ ๋๊ฒผ๋ค.)
# ์ถ์ฒ: https://www.acmicpc.net/source/83166630
from collections import deque
import sys
input = sys.stdin.readline
def bfs(r,c):
dist = [[0] * m for _ in range(n)]
dr = [-1,1,0,0]
dc = [0,0,-1,1]
visited[r][c] = True
queue = deque()
queue.append((r,c))
while queue:
r, c = queue.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
if 0 <= nr < n and 0 <= nc < m and board[nr][nc] == 'L' and not visited[nr][nc]:
dist[nr][nc] = dist[r][c] + 1
visited[nr][nc] = True
queue.append((nr,nc))
return max(map(max,dist))
n, m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
answer = 0
for i in range(n):
for j in range(m):
if board[i][j] == 'L':
visited = [[False] * m for _ in range(n)]
if 0 <= i - 1 and i + 1 < n:
if board[i - 1][j] == 'L' and board[i + 1][j] == 'L':
continue
if 0 < j - 1 and j + 1 < m:
if board[i][j - 1] == 'L' and board[i][j - 1] == 'L':
continue
answer = max(answer, bfs(i, j))
print(answer)
๋จผ์ ํ์ฌ ์ก์ง์ ์ํ์ข์ฐ๊ฐ ๋ฒ์ ๋ด์ ์๋์ง ์ฒดํฌํ๊ณ ,
์ํ ๋๋ ์ข์ฐ์ L์ด ์กด์ฌํ๋ค๋ฉด ๋ฐ๋ก ๋ค์ ๋ฐ๋ณต๋ฌธ์ผ๋ก ๋์ด๊ฐ๋ค.
if 0 <= i - 1 and i + 1 < n:
if board[i - 1][j] == 'L' and board[i + 1][j] == 'L':
continue
if 0 < j - 1 and j + 1 < m:
if board[i][j - 1] == 'L' and board[i][j - 1] == 'L':
continue
๋ด ์๋ ์ฝ๋๋ก๋ Python3 ํต๊ณผ๊ฐ ๊ฐ๋ฅํ์ง๋ง, ๐์ ํ์ด๊ฐ ํจ์ฌ ๋ ํจ์จ์ ์ด๋ค.
๋ฌธ์ ๊ฐ ์๊ตฌํ๋ ๋ต์ ๋ ๊ฐ๊น๊ธฐ๋ ํ ๊ฒ ๊ฐ๋ค.
์กฐ๊ธ๋ง ๋ ์๊ฐํ๋ฉด ๋ ์ฌ๋ฆด ์ ์๋ ํ์ด๋ค.
ํ์์ ๊น์ด ์๊ฐํ๋ ์ต๊ด์ ๊ธธ๋ฌ์ผ๊ฒ ๋ค...