[baekjoon] 1987 알파벳 (Javascript,Python)

1987번: 알파벳 (acmicpc.net)

1987번: 알파벳

---

알고리즘 : dfs, 백트래킹

 

이제 조금씩 dfs 백트래킹에 익숙해지고 있는 것 같다!

이번문제는 파이썬에서 시간초과로 고생을 많이했는데 pypy3로 제출하니까 간단히 해결되었다... 내시간...

 

- Javascript

function solution() {
  let input = require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .split("\n")
    .map((val) => val.trim());

  let [n, m] = input
    .shift()
    .split(" ")
    .map((v) => +v);

  let board = input.map((v) => v.split(""));

  // 0,0은 말이 놓여져있음
  // 상하좌우, 같은 알파벳은 없어야한다.

  let vis = new Array(26).fill(0);

  let ans = 0;

  let dx = [0, 1, 0, -1];
  let dy = [1, 0, -1, 0];
  const dfs = (x, y, cnt) => {
    ans = Math.max(ans, cnt);
    vis[board[x][y].charCodeAt() - 65] = 1;
    for (let dir = 0; dir < 4; dir++) {
      let nx = x + dx[dir];
      let ny = y + dy[dir];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if (vis[board[nx][ny].charCodeAt() - 65] === 0) {
        vis[board[nx][ny].charCodeAt() - 65] = 1;
        dfs(nx, ny, cnt + 1);
        vis[board[nx][ny].charCodeAt() - 65] = 0;
      }
    }
  };

  dfs(0, 0, 1);

  console.log(ans);
}

solution();

 

- Python

import sys

sys.stdin = open("baekjoon/1987/input.txt","r")

n,m = map(int,input().split(" "))

board = [list(map(lambda a : ord(a)-65,input())) for _ in range(n)]
ans=0

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

vis = [0]*26


def dfs (x,y,cnt):
    global ans
    if ans<cnt:
        ans = cnt
    vis[board[x][y]] =1
    for dir in range(4):
        nx = x+dx[dir]
        ny = y+dy[dir]
        if 0 <= nx < n and 0 <= ny < m and vis[board[nx][ny]] == 0:
            vis[board[nx][ny]]=1
            dfs(nx,ny,cnt+1)
            vis[board[nx][ny]]=0


dfs(0,0,1)

print(ans)