1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
아이디어:
백트래킹과 DFS를 사용하여 구현하였다. 내가 이해한 방식이 맞는 지는 모르겠지만.. 일단 재귀함수로 구현하였고, pypy로 통과했다.
조건은 크게 어렵지 않았던 것 같다. 차근차근히 풀면 풀어졌다.
최댓값을 갱신하는 부분과, DFS에서 돌아온 후에 True를 다시 False로, cnt--를 해주는 것에 유의하자. (이 부분을 if문 밖에 써서 삽질을 했었다.) + 좌표 범위 체크하는 조건도!
#1987번 알파벳
import sys
R, C = map(int, sys.stdin.readline().split())
visit = [False]*26
board = [['0'] for _ in range(R+1)]
board[0] = ['0']*(C+1)
for i in range(1,R+1):
board[i]+=list(sys.stdin.readline().rstrip())
xx = [1, -1, 0, 0]
yy = [0, 0, 1, -1] #상하좌우 움직이는 x,y좌표
cnt = 0
ans = 0
def DFS(X, Y):
global cnt, ans
cnt+=1
ans = max(ans, cnt)
r,c = Y,X
visit[ord(board[r][c])-65] = True
for i in range(4):
x = c + xx[i]
y = r + yy[i]
if (x>=1 and x<=C and y>=1 and y<=R): #범위 체크
if (visit[ord(board[y][x])-65]==False):
visit[ord(board[y][x])-65] = True
DFS(x,y)
visit[ord(board[y][x])-65] = False
cnt-=1
DFS(1,1)
print(ans)
'알고리즘💻 > 그래프(DFS&BFS)' 카테고리의 다른 글
BOJ 10971번: 외판원 순회 2 (0) | 2021.05.12 |
---|---|
BOJ 19621번: 회의실 배정2 (0) | 2021.05.12 |
BOJ 2606번: 바이러스 (0) | 2021.02.08 |
5829번: Luxury River Cruise (0) | 2021.02.08 |
BOJ 19538번: 루머 (0) | 2021.02.07 |