프로그래머스 - 바탕화면 정리하기

문제 설명

코딩테스트를 준비하는 머쓱이는 프로그래머스에서 문제를 풀고 나중에 다시 코드를 보면서 공부하려고 작성한 코드를 컴퓨터 바탕화면에 아무 위치에나 저장해 둡니다. 저장한 코드가 많아지면서 머쓱이는 본인의 컴퓨터 바탕화면이 너무 지저분하다고 생각했습니다. 프로그래머스에서 작성했던 코드는 그 문제에 가서 다시 볼 수 있기 때문에 저장해 둔 파일들을 전부 삭제하기로 했습니다.

컴퓨터 바탕화면은 각 칸이 정사각형인 격자판입니다. 이때 컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 wallpaper가 주어집니다. 파일들은 바탕화면의 격자칸에 위치하고 바탕화면의 격자점들은 바탕화면의 가장 왼쪽 위를 (0, 0)으로 시작해 (세로 좌표, 가로 좌표)로 표현합니다. 빈칸은 ".", 파일이 있는 칸은 "#"의 값을 가집니다. 드래그를 하면 파일들을 선택할 수 있고, 선택된 파일들을 삭제할 수 있습니다. 머쓱이는 최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우려고 하며 드래그로 파일들을 선택하는 방법은 다음과 같습니다.

• 드래그는 바탕화면의 격자점 S(lux, luy)를 마우스 왼쪽 버튼으로 클릭한 상태로 격자점 E(rdx, rdy)로 이동한 뒤 마우스 왼쪽 버튼을 떼는 행동입니다. 이때, "점 S에서 점 E로 드래그한다"고 표현하고 점 S와 점 E를 각각 드래그의 시작점, 끝점이라고 표현합니다.

• 점 S(lux, luy)에서 점 E(rdx, rdy)로 드래그를 할 때, "드래그 한 거리"는 |rdx - lux| + |rdy - luy|로 정의합니다.

• 점 S에서 점 E로 드래그를 하면 바탕화면에서 두 격자점을 각각 왼쪽 위, 오른쪽 아래로 하는 직사각형 내부에 있는 모든 파일이 선택됩니다.

예를 들어 wallpaper = [".#...", "..#..", "...#."]인 바탕화면을 그림으로 나타내면 다음과 같습니다.

이러한 바탕화면에서 다음 그림과 같이 S(0, 1)에서 E(3, 4)로 드래그하면 세 개의 파일이 모두 선택되므로 드래그 한 거리 (3 - 0) + (4 - 1) = 6을 최솟값으로 모든 파일을 선택 가능합니다.

(0, 0)에서 (3, 5)로 드래그해도 모든 파일을 선택할 수 있지만 이때 드래그 한 거리는 (3 - 0) + (5 - 0) = 8이고 이전의 방법보다 거리가 늘어납니다.

머쓱이의 컴퓨터 바탕화면의 상태를 나타내는 문자열 배열 wallpaper가 매개변수로 주어질 때 바탕화면의 파일들을 한 번에 삭제하기 위해 최소한의 이동거리를 갖는 드래그의 시작점과 끝점을 담은 정수 배열을 return하는 solution 함수를 작성해 주세요. 드래그의 시작점이 (lux, luy), 끝점이 (rdx, rdy)라면 정수 배열 [lux, luy, rdx, rdy]를 return하면 됩니다.

---

제한사항

• 1 ≤ wallpaper의 길이 ≤ 50
• 1 ≤ wallpaper[i]의 길이 ≤ 50
  • wallpaper의 모든 원소의 길이는 동일합니다.
• wallpaper[i][j]는 바탕화면에서 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
• wallpaper[i][j]는 "#" 또는 "."의 값만 가집니다.
• 바탕화면에는 적어도 하나의 파일이 있습니다.
• 드래그 시작점 (lux, luy)와 끝점 (rdx, rdy)는 lux < rdx, luy < rdy를 만족해야 합니다.

---

입출력 예

wallpaper	result
[".#...", "..#..", "...#."]	[0, 1, 3, 4]
["..........", ".....#....", "......##..", "...##.....", "....#....."]	[1, 3, 5, 8]
[".##...##.", "#..#.#..#", "#...#...#", ".#.....#.", "..#...#..", "...#.#...", "....#...."]	[0, 0, 7, 9]
["..", "#."]	[1, 0, 2, 1]

---

입출력 예 설명

입출력 예 #1

• 문제 설명의 예시와 같은 예제입니다. (0, 1)에서 (3, 4)로 드래그 하면 모든 파일을 선택할 수 있고 드래그 한 거리는 6이었고, 6보다 적은 거리로 모든 파일을 선택하는 방법은 없습니다. 따라서 [0, 1, 3, 4]를 return합니다.

입출력 예 #2

• 예제 2번의 바탕화면은 다음과 같습니다.

  

  (1, 3)에서 (5, 8)로 드래그하면 모든 파일을 선택할 수 있고 이보다 적은 이동거리로 모든 파일을 선택하는 방법은 없습니다. 따라서 가장 적은 이동의 드래그로 모든 파일을 선택하는 방법인 [1, 3, 5, 8]을 return합니다.

입출력 예 #3

• 예제 3번의 바탕화면은 다음과 같습니다.

  

  모든 파일을 선택하기 위해선 바탕화면의 가장 왼쪽 위 (0, 0)에서 가장 오른쪽 아래 (7, 9)로 드래그 해야만 합니다. 따라서 [0, 0, 7, 9]를 return합니다.

입출력 예 #4

• 예제 4번의 바탕화면은 다음과 같이 2행 1열에만 아이콘이 있습니다.

  

  이를 드래그로 선택하기 위해서는 그 칸의 왼쪽 위 (1, 0)에서 오른쪽 아래 (2, 1)로 드래그 하면 됩니다. (1, 0)에서 (2, 2)로 드래그 해도 아이콘을 선택할 수 있지만 이전보다 이동거리가 늘어납니다. 따라서 [1, 0, 2, 1]을 return합니다.

---

소마 테스트가 프로그래머스에서 진행된다길래 맛 좀 보려고 놀러왔습니다.
어려울 것 없는 간단한 리스트 활용 문제입니다.

wallpaper에서 #이 가장 빨리 나오는 인덱스가 첫번째 x, 가장 나중에 나오는 인덱스가 두번째 x, wallpaper의 원소들 중에서 #이 가장 빠른 위치에 있는 인덱스가 첫번째 y, 마찬가지로 가장 나중에 나오는 인덱스가 두번째 y라고 생각하시면 됩니다.

from collections import deque

def solution(wallpaper):
    x = []
    y = []
    sum = 0

deque 하나 import 하고 시작하겠습니다.

    wallpaper = deque(wallpaper)
    while wallpaper:
        tmp = wallpaper.popleft()
        if '#' in tmp:
            x.append(sum)

popleft를 통해 개별 원소마다 접근하고
위에 언급한대로 wallpaper의 요소들중에 #이 있다면 sum값을 활용해서 해당 인덱스를 x 리스트에 싹 다 기록합니다.

        for values in tmp:
            if values == '#':
                y.append(sum2)
            sum2 += 1
        sum += 1

개별 원소 안에 #이 존재한다면 해당 위치를 y리스트에 싹 다 기록합니다.

    return [min(x),min(y),max(x)+1,max(y)+1]

마지막으로 값 return 해주면 됩니다.

---

프로그래머스 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

---

def solution(begin, target, words):
global ans
words = list(sorted(words))
  

일단 정렬한 값과 정렬하지 않은 값이 다를 수 있기 때문에 단어 리스트 정렬부터 해줍시다.

begin: hit target: cog words: [hot, dot, dog, lot, log, cog] return : 4 << 예제 1번
begin: hit target: cog words: [cog, log, lot, dog, dot, hot] return : 4

와 같은 경우에요.

    def dfs(begin):
     global ans
     if begin in words:
         visited[words.index(begin)] = 1 

DFS 작성을 시작합니다.
현재 탐색중인 단어를 방문처리 해줍시다.

        sum = 0
        for k in range(len(begin)):
            if begin[k] != target[k]:
                sum += 1
        if sum == 1:
            return ans

현재 탐색중인 단어와 타겟 단어가 문자 1개 차이로 틀리다면 타겟 단어로 갈 수 있다는 것을 의미하므로 재귀를 끝내줍시다.

        for i in range(len(words)):
            sum2 = 0
            for j in range(len(words[i])):
                if words[i][j] != begin[j]:
                    sum2 += 1
            if sum2 == 1 and not visited[i]:
                print(words[i])
                ans += 1
                dfs(words[i])
                return ans

words 리스트에서 하나씩 꺼내서 만약 현재 탐색중인 단어하고 문자 1개 차이로 틀린 단어가 있다면 해당 단어를 탐색에 넣어 재귀를 돌려줍시다. 상단 코드에서 타켓 단어로 가는 것이 증명되었다면(dfs(words[i]) 아래 부분) ans를 return 하여 함수를 끝내주도록 합시다.

    ans = 1
    visited = [0] * len(words)
    if target not in words:
        return 0
    else:
        return dfs(begin)

target이 리스트 안에 없으면 타겟단어를 아예 만들 수 없는 것이므로 0을 return 하고 아니라면 dfs(begin)에서 나온 ans값을 return 하면 타겟단어까지 가는데 걸리는 단어 수 출력이 가능합니다.

---

---

프로그래머스 - 등굣길

10억이 넘는 수로 나누라는 것을 보자마자 알았습니다.
네, DP 문제입니다.
물웅덩이로는 통행이 불가하며 집에서 학교까지 가는 최적의 값을 도출하는 문제입니다.

---

분석

저는 DP문제는 분석을 안하면 항상 푸는 데 난이도가 있더라고요.
해당 문제는 쟁점이 하나 있습니다. 바로 물웅덩이가 1열/1행에 생기는 경우입니다.

https://velog.io/@ghost_dog/%EA%B3%B5%EB%B6%80-2024.02.15-%EC%BD%94%EB%94%A9-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4

왜 1행/1열에 이해가 안가시면 이 게시물 한번 읽어보시면 도움되실 겁니다.

최단거리를 구하기 위해 1행과 1열을 전부 1로 초기화 시키고 있습니다.
근데 어라? 물웅덩이가 1행과 1열에 생겼습니다. 그럼 이 이후는 어떻게 처리해야 할까요?

정답은 장애물이 생긴 이후의 1행 또는 1열은 다 0으로 초기화해야 한다 입니다.
왜냐하면 장애물이 생긴 이후의 공간은 어차피 오른쪽 또는 하강만 가능하므로 방문을 해봐야 최단 거리를 구하는 데 있어 전혀 메리트가 없기 때문입니다. (학교가 맨 아래 오른쪽에 있으니까)

---

코딩

해당 내용을 생각하며 코딩을 해봅시다.

def solution(m, n, puddles):
    graph = [[0]*m for _ in range(n)]
    
    for a in range(len(graph[0])):
        if [a+1,1] not in puddles:
            graph[0][a] = 1
        else:
            break
    for b in range(len(graph)):
        if [1,b+1] not in puddles: 
            graph[b][0] = 1
        else:
            break

행,열,물웅덩이 위치를 받고 행열 크기만큼의 원소가 전부 0인 그래프를 생성해줍시다.
만약 웅덩이가 없는 1행/1열이라면 해당 인덱스는 1로 초기화해주고
행열 인덱스 값 1로 초기화중에 1행/1열 자리에 웅덩이가 발생했다! 하면 break로 나와서 원래 값인 0으로 냅둡시다.

    for i in range(len(graph)):
        for j in range(len(graph[0])):
            if i==0 or j==0:
                continue

이제 DP를 돌릴 준비를 합시다.
각 인덱스마다 탐색을 하면서 만약 1행 또는 1열에 접근했다면 점화식을 위한 초기값이므로 건들지 말고 continue를 해줍시다. (어차피 1행 또는 1열은 가는 경우의 수가 1가지밖에 없으므로)

            elif [j+1,i+1] in puddles:
                continue

웅덩이라면 건들지 말고 continue 해줍니다. 이러면 점화식 적용이 안되어 왼쪽+위쪽 이전위치 최단거리 점화식을 사용할 때 이전위치의 웅덩이는 최단거리값이 아예 없는 효과를 줍니다.

            else:
                graph[i][j] = graph[i-1][j] + graph[i][j-1]

마지막으로 최단거리 구하는 점화식 자기자신 최단거리 = 위인덱스 최단거리 + 왼쪽인덱스 최단거리
를 작성해주면 됩니다.

    return graph[n-1][m-1]%1000000007

출력은 DP 초과를 방지하기 위해 10억인가? 를 나눈 나머지를 출력하라고 문제에 명시되어있습니다.
문제 취지는 좋은데 웅덩이 행 열이 뒤바껴서 들어가는 등 좀 미흡한 부분이 존재하는 문제였던 것 같습니다.

---

---