출처: [백준] 1987번 알파벳
시간 제한
메모리 제한
제출
정답
맞은 사람
정답 비율
2 초
256 MB
49798
15713
9586
29.155%
문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력 첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
예제 입력 1 예제 출력 1 기타 입력 기타 출력 출처 Olympiad > Croatian Highschool Competitions in Informatics > 2002 > Regional Competition - Juniors 3번
링크
알고리즘 분류
풀이
소스코드_DFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import sysinput = sys.stdin.readlinedx = [-1 , 1 , 0 , 0 ] dy = [0 , 0 , -1 , 1 ] def dfs (x, y, count ): global ans ans = max (ans, count) for i in range (4 ): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < R and 0 <= ny < C and passed[board[nx][ny]] == 0 : passed[board[nx][ny]] = 1 dfs(nx, ny, count + 1 ) passed[board[nx][ny]] = 0 R, C = map (int , input ().split()) board = [list (map (lambda x: ord (x) - 65 , input ().rstrip())) for _ in range (R)] passed = [0 ] * 26 ans = 1 passed[board[0 ][0 ]] = 1 dfs(0 , 0 , ans) print (ans)
소스코드_BFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import sysinput = sys.stdin.readlinedx = [-1 , 1 , 0 , 0 ] dy = [0 , 0 , -1 , 1 ] def bfs (): global count queue = set () queue.add((0 , 0 , board[0 ][0 ])) while queue: x, y, ans = queue.pop() 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 ans: queue.add((nx, ny, ans + board[nx][ny])) count = max (count, len (ans) + 1 ) R, C = map (int , input ().split()) board = [list (input ().rstrip()) for _ in range (R)] count = 1 bfs() print (count)
소스코드_실패(메모리 초과) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import syssys.setrecursionlimit(10 ** 6 ) input = sys.stdin.readlinedx = [-1 , 1 , 0 , 0 ] dy = [0 , 0 , -1 , 1 ] def dfs (x, y, cnt ): global count count = max (cnt, count) 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 passed: passed.append(board[nx][ny]) dfs(nx, ny, cnt + 1 ) passed.append(board[nx][ny]) R, C = map (int , input ().split()) board = [list (input ().rstrip()) for _ in range (R)] passed = [] count = 1 dfs(0 , 0 , count) print (count)
![[백준] 15652번 N과 M (4)](/images/posts/thumb/baekjoon.png)