문제 정보
https://www.acmicpc.net/problem/2589
문제
보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.
예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.
보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.
출력
첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.
접근방법
1. 가로 세로 크기가 작기 때문에 모든 좌표를 확인해야 할 것 같다.
브루트포스로 배열의 모든 좌표에 접근하자
2중 for 문을 통해서 접근할 수 있을 것 같다.
2. 4방향을 탐색해야 한다.
상,하,좌,우 델타를 이용하자. 탐색에 정해진 순서가 따로 존재하지 않기 때문에
아무렇게나 대충 상하좌우 맞춰서 적으면 된다(사실 헷갈려서 생각하고싶지 않았음)
3. 최단거리를 찾는 문제 -> bfs 를 사용하자
일단은 일반적인 bfs 코드를 작성하고 추가적인 코드는 나중에 생각하자.
덱 모듈을 불러와서 덱을 만들고, 방문체크를 위해서 방문배열을 생성하자
덱에 bfs 로 들어온 좌표를 넣어주고, 현재 위치를 방문체크 해주자
덱에 요소가 없을때까지 while 을 이용하고 nr,nc가 땅이면 nr,nc를 덱에 넣어주자
4. 그런데 보물은 최장거리에 있다. 어떻게 할까?
문제의 핵심 키워드인 것 같았다. 예제의 경우
[3][1] [4][1] 에 보물이 있다고 한다
잘못된 생각 -
처음에는 bfs 탐색을 할 때 한칸 이동할 때 마다 cnt 값을 증가시켜서
보물이 묻혀있을 가능성이 있는 모든 위치를 max 메서드를 통해서 리스트에 추가하고
bfs 탐낸 후 set 으로 중복값을 제거하고 cnt 값이 가장 큰 두 위치를 찾아서
이를 기준으로 다시 bfs 를 하려고 했다.
bomul = []
bomul.append(cnt, nr, nc)
# 원래는 이런식 으로 해서 가장 거리가 먼 육지의 위치를 찾아서 bfs를 다시 돌리려 함
하지만 굳이 그럴필요 없이 방문배열의 값을 1씩 증가시켜주면서
배열의 가장 큰 값을 찾아주면 가장 멀리 떨어져있는 위치를 찾아가는 최소시간을 찾을 수 있다.
1차 풀이(오답)
import sys;
from collections import deque
# 걍 아무 거나 때려 넣음
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
def bfs(i, j):
bomul = []
cnt = 0
visted = [[0] * c for _ in range(r)]
q = deque()
visted[i][j] = 1
q.append((i, j))
while q:
sr1, sc1 = q.popleft()
for d in range(4):
nr = sr1 + dr[d]
nc = sc1 + dc[d]
# 범위체크 해주고, 움직이는 위치가 땅일때만 가고, 아직 방문 안했고
if 0 <= nr < r and 0 <= nc < c and zido[nr][nc] == 'L' and visted[nr][nc] == 0:
cnt += 1
visted[nr][nc] = visted[sr1][sc1] + 1
q.append((nr, nc))
bomul = max(max(visted))
return bomul-1
r, c = map(int, input().split())
zido = [input() for _ in range(r)]
bomul2 = []
for sr in range(r):
for sc in range(c):
# 육지일때만 거리찾으러 가야됨
if zido[sr][sc] == 'L':
find = bfs(sr, sc)
bomul2.append(find)
print(max(bomul2))
bfs 탐색을 끝마치고 리턴받은 값을 빈 리스트에 추가해서
그 중 최대값을 찾으려고 했다.
처음엔 시간초과 부분이
find = bfs(sr, sc)
bomul2.append(find)
여기라고 생각했다.
from collections import deque
# 걍 아무 거나 때려 넣음
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
def bfs(i, j):
bomul = 0
visted = [[0] * c for _ in range(r)]
q = deque()
visted[i][j] = 1
q.append((i, j))
while q:
sr1, sc1 = q.popleft()
for d in range(4):
nr = sr1 + dr[d]
nc = sc1 + dc[d]
# 범위체크 해주고, 움직이는 위치가 땅일때만 가고, 아직 방문 안했고
if 0 <= nr < r and 0 <= nc < c and zido[nr][nc] == 'L' and visted[nr][nc] == 0:
visted[nr][nc] = visted[sr1][sc1] + 1
q.append((nr, nc))
bomul = max(max(visted))
return bomul - 1
cnt = 0
r, c = map(int, input().split())
zido = [input() for _ in range(r)]
for sr in range(r):
for sc in range(c):
# 육지일때만 거리찾으러 가야됨
if zido[sr][sc] == 'L':
find = bfs(sr, sc)
if cnt <= find:
cnt = find
print(cnt)
그래서 이번엔 cnt 변수에 0 을 할당하고
이를 기준으로 최대값을 찾아주었다.
find = bfs(sr, sc)
if cnt <= find:
cnt = find
하지만 똑같이 시간초과
2차 풀이(정답)
from collections import deque
# 걍 아무 거나 때려 넣음
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
def bfs(i, j):
bomul = 0
visted = [[0] * c for _ in range(r)]
q = deque()
visted[i][j] = 1
q.append((i, j))
while q:
sr1, sc1 = q.popleft()
for d in range(4):
nr = sr1 + dr[d]
nc = sc1 + dc[d]
# 범위체크 해주고, 움직이는 위치가 땅일때만 가고, 아직 방문 안했고
if 0 <= nr < r and 0 <= nc < c and zido[nr][nc] == 'L' and visted[nr][nc] == 0:
visted[nr][nc] = visted[sr1][sc1] + 1
bomul = max(bomul, visted[nr][nc])
q.append((nr, nc))
return bomul - 1
cnt = 0
r, c = map(int, input().split())
zido = [input() for _ in range(r)]
for sr in range(r):
for sc in range(c):
# 육지일때만 거리찾으러 가야됨
if zido[sr][sc] == 'L':
find = bfs(sr, sc)
if cnt <= find:
cnt = find
print(cnt)
아무래도 문제는
bomul = max(max(visted))
이었던 것 같다.
max를 두번이나 사용하다 보니 행의 최대 열의 최대를 계속해서 탐색하다 보니
메서드를 계속해서 사용해서 시간 초과가 난 것 같다.
bomul = max(bomul, visted[nr][nc])
를 사용해서 둘의 최대값을 bomul으로 삼는 방식으로 했다.
예를들어 visted[nr][nc] 이 1, 3, 2 인 경우를 가정하면
처음에 bomul 은 0 이기 때문에
max(0, 1) = > bomul = 1
max(1, 3) = > bomul = 3
max(3, 2) = > bomul = 3
이런 식으로 진행되기 때문에 최대값 - 1 을 리턴해줄 수 있다.
max 메서드를 사용하지 않으려면
if bomul < visted[nr][nc]:
bomul = visted[nr][nc]
처럼 사용해도 될 것 같다.
느낀점
시간초과 진짜 개킹받네;;;
bfs를 풀때 전형적인 구조는 어느정도 감이 잡힌 것 같다.
dfs는 언제하지ㅋㅋㅋㅋㅋㅋㅋㅋ
트리의 지름 풀다가 포기하고 다른 스터디 문제로 푼건데 풀려서 다행이다
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 1967 트리의 지름 (파이썬) (0) | 2022.09.21 |
---|---|
백준 1181 단어 정렬 (파이썬) (0) | 2022.09.20 |
백준 1991 트리 순회 (파이썬) (0) | 2022.09.12 |
백준 17298 오큰수 (파이썬) (0) | 2022.09.12 |
백준 1759 암호 만들기 (파이썬) (0) | 2022.09.09 |