1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
코드
- 정답 코드
import sys
input = sys.stdin.readline
r, c = map(int, input().split())
board = []
for _ in range(r):
board.append(input())
ans = 1
def bfs():
global ans
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = set([(0, 0, board[0][0])])
while q:
x, y, route = q.pop()
ans = max(ans, len(route))
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] not in route:
q.add((nx, ny, route + board[nx][ny]))
bfs()
print(ans)
시간 초과를 정말 많이 본 문제였다...
처음에 풀이는
r, c = map(int, input().split())
board = []
for _ in range(r):
board.append(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [board[0][0]]
def dfs(x, y, visited, num):
res = num
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] not in visited:
new_visited = visited + [board[nx][ny]]
res = max(res, dfs(nx, ny, new_visited, num + 1))
return res
print(dfs(0,0,visited, 1))
dfs를 이용하여 풀이하려 했다. 지나온 알파벳을 배열에 저장하고 배열에 저장되어 있지 않은 알파벳이 저장된 칸이라면 계속해서 탐색하는 방법으로 구현하려 했다. dfs를 오랜만에 했더니 잘 기억이 나지 않아 재귀적으로 dfs를 다시 부를 때 지나온 배열을 넘겨주는걸 어떻게 할까 하다가 처음에는 위와 같이 했는데 이렇게 하면 계속 새로운 배열을 만들어서 넘겨주기 때문에 메모리상 정말 비효율적인 코드일 것이다. 그래서 전에 정리해놨던 dfs 코드를 참고 + 구글링하다 얼핏 보니 집합을 이용하는 것 같아서 아래와 같이 구현하고 제출했는데 역시나 시간 초과가 떴다...
r, c = map(int, input().split())
board = []
for _ in range(r):
board.append(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = set([board[0][0]])
ans = 0
def dfs(x, y, visited, num):
global ans
ans = max(ans, num)
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] not in visited:
visited.add(board[nx][ny])
dfs(nx, ny, visited, num+1)
visited.remove(board[nx][ny])
dfs(0,0,visited, 1)
print(ans)
이걸 하며 파이썬의 자료구조들의 시간 복잡도가 궁금해져서 찾아봤는데 여기서 사용한 포함 여부를 확인하는 연산의 경우 평균적으로 list 자료형은 시간 복잡도가 O(N), set와 dict 자료형은 O(1)의 시간 복잡도를 가진다고 한다.
각 자료형의 다른 연산들에 대한 시간 복잡도는 아래의 링크에서 확인 가능하다.
https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
계속 해도 시간 초과로 안돼서 그냥 다른 사람들은 어떻게 했나 찾아봤다. 그랬더니 맨 위의 정답 코드와 같은 풀이를 알게 되었다. 그런데 지금 봐도 잘 이해가 안된다. 내가 풀이한 코드에서도 이미 방문한 알파벳이면 visited에 저장하여 더이상 탐색되지 않도록 처리를 해주었고 정답 코드와 그와 유사한거 같은데 왜 안되는지...
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 2573번 빙산 (0) | 2022.09.16 |
---|---|
[Python] 백준 2239번 스도쿠 (0) | 2022.08.16 |
[Python] 백준 12852번 1로 만들기 2 (0) | 2022.08.03 |
[Python] 백준 4963번 섬의 개수 (0) | 2022.01.22 |
[Python/파이썬] 백준 2644번 촌수계산 (0) | 2022.01.17 |