BOJ_1987 알파벳

TOC {:toc}

이 글은 백준 온라인 저지의 1987번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.22 (Python)

메모리	시간	코드 길이
194376 KB	7324 ms	594 B

단계	시작 시각	끝난 시각
문제 이해	20:04:40	20:09:13
풀이 생각	20:37:38	21:20:27
코딩	21:20:35	21:51:13
디버깅	21:51:38	22:14:44

import sys
input = lambda: sys.stdin.readline().rstrip()

R, C = map(int, input().split())
board = [list(map(lambda x: ord(x) - 65, input())) for _ in range(R)]
visited = [0] * 26
visited[board[0][0]] = 1

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def dfs(x, y, l):
    global max_len
    max_len = max(l, max_len)

    for k in range(4):
        i = x + dx[k]
        j = y + dy[k]

        if 0 <= i < R and 0 <= j < C and not visited[board[i][j]]:
            visited[board[i][j]] = 1
            dfs(i, j, l + 1)
            visited[board[i][j]] = 0


max_len = 1
dfs(0, 0, 1)

print(max_len)

아이디어 & 풀이

백 트래킹을 이용하는 문제이다.

입력받은 보드를 이차원 리스트로 구성한 뒤 dfs를 이용해 현재 보드의 상하좌우를 돌면서 방문한다.

사용한 문자를 확인할 때, 딕셔너리나 리스트 안에 해당 문자가 있는지 확인하는 것보다 참/거짓을 확인하는 것이 시간이 적게 소요된다.
visited 같은 True / False 리스트를 구성하려면 (e.g., visited[A] == True) 입력받은 알파벳이 각 인덱스가 되어야 하고 이를 위해서 A ~ Z까지의 문자를 0 ~ 25의 숫자로 치환해주는 것이 효율적이다.
lambda를 이용해서 아스키코드로 치환한 뒤 A의 값인 65를 빼준 값으로 매핑해 보드를 구성한다.

해당 알파벳을 이전에 이미 사용했으면 더는 탐색하지 않고 drop 한다.

디버그

처음에 문자 그대로 입력받아서 사용 여부를 확인했더니 시간초과가 났다.
- 위의 풀이처럼 입력받은 문자를 숫자로 치환해서 검사를 진행했다.
입력받은 문자열의 문자 각각을 리스트로 만들기 때문에 readline()을 사용할 경우 rstrip() 해줘야 한다.
상하좌우 방문을 for i, j in ((x + 1, y), (x, y + 1), ...)의 꼴로 했는데 이 역시 시간초과가 나서 위와 같이 바꿔주었다.

피드백

이번 문제에서는 왜 dfs를 스택으로 시도하지 않았을까.

2022.04.08 (JS)

메모리	시간	코드 길이
11092 KB	1652 ms	978 B

단계	시작 시각	끝난 시각
문제 이해	00:19:03	00:20:22
풀이 생각	00:20:23	00:22:39
코딩	00:22:40	01:08:06
디버깅	11:13:22	11:43:19

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

function main() {
    function dfs(x, y, count) {
        const dx = [1, 0, -1, 0];
        const dy = [0, -1, 0, 1];

        for (let i = 0; i < 4; i += 1) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (0 <= nx && nx < C && 0 <= ny && ny < R && !isVisited[board[ny][nx]]) {
                isVisited[board[ny][nx]] = true;
                dfs(nx, ny, count + 1);
                isVisited[board[ny][nx]] = false;
            } else {
                max = Math.max(count, max);
            }
        }
    }

    const isVisited = Array(26).fill(false);

    let max = 0;
    isVisited[board[0][0]] = true;
    dfs(0, 0, 1);

    return max;
}

const [RC, ...lines] = input;
const [R, C] = RC.split(" ").map((n) => parseInt(n));
const board = lines.map((line) => line.split("").map((c) => c.charCodeAt(0) - 65));

console.log(main());

디버그

일반적인 dfs는 isVisited를 모든 경로에서 공유하기 때문에 생성되는 경로마다 별도로 isVisited를 관리할 방법을 찾다가 지금까지 지나온 문자열을 인자로 넘겨서 해당 문자열에 현재 값이 있는지 확인하는 방식으로 작성했는데 결국 마지막쯤에서 시간초과됐다.
isVisited를 관리하는게 나을 것 같았는데 방법을 제대로 못 찾았다.
핵심은 dfs 함수로 전달하기 전에 해당 문자의 isVisited를 true 으로 바꾸고 전달해서 실행한 다음에 다시 false로 돌려놓는 것

피드백

isVisited를 배열로 관리하려다 보니 board를 순회할 때마다 이 값을 숫자로 변경하면 시간 낭비가 심할 것 같아서 isVisited를 문자가 key인 객체로 만들었는데, board의 값을 숫자로 바꾸는게 훨씬 나은 방법이었다.

참고 답안 0

import sys

input = lambda: sys.stdin.readline().strip()

r, c = map(int, input().split())
a = [list(map(lambda x: ord(x) - 65, input())) for i in range(r)]
ch = [0] * 26

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def dfs(x, y, z):
    global answer
    answer = max(answer, z)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < r and 0 <= ny < c and ch[a[nx][ny]] == 0:
            ch[a[nx][ny]] = 1
            dfs(nx, ny, z + 1)
            ch[a[nx][ny]] = 0


answer = 1
ch[a[0][0]] = 1
dfs(0, 0, answer)

print(answer)

아이디어 & 풀이

풀이 방식은 동일한데 위의 풀이가 가장 시간이 적게 걸린다.

참고 답안 1

import sys
input = lambda: sys.stdin.readline().rstrip()

def bfs():
    mx = 0
    queue = set([(0, 0, board[0][0])])

    while queue:
        x, y, word = queue.pop()
        mx = max(mx, len(word))
        if mx == 26:
            return 26

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < R and 0 <= ny < C and not board[nx][ny] in word:
                queue.add((nx, ny, word + board[nx][ny]))

    return mx


R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]

dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)

print(bfs())

아이디어 & 풀이

bfs에 재귀 대신 스택을 이용한다.

스택에 리스트 대신 집합 자료구조를 이용해 중복 방문을 최소화한다.
지금까지 만든 단어를 함수의 인자를 보내 이 안에 현재 받은 문자가 있는지 확인한다.