Algorithm TIL (240920)

> [백준] 동방 프로젝트 (14594)

https://www.acmicpc.net/problem/14594

 

 

문제 풀이 과정

• 빌딩에 방이 있고, 그 방과 방 사이의 벽을 허물면 하나의 방이 된다라는 문제 의도를 읽고
• 배열로 방을 만들고 현재 방과 다음 방 사이의 벽 유무를 1로 표시했다. 빌런이 벽을 부수면 0이 된다.

문제 풀이

python

n = int(input()) # 동아리방의 개수
m = int(input()) # 종빈빌런의 행동횟수
building = [1] * (n+1) # 동아리방
for i in range(m) :
    x, y = map(int, input().split()) # x번방부터 y번 방 사이의 벽을 무너뜨린다.
    
    for idx in range(x+1, y+1) :
        building[idx] = 0

ans = 0
for bang in building[1:n+1] :
    if bang == 1 :
        ans+=1
print(ans)

 

 

---

 

> [백준] 지구온난화 (5212)

https://www.acmicpc.net/problem/5212

 

문제 풀이 과정

• 문제가 애매모호해서 조건을 이해하는 데 조금 시간이 걸렸다.
• 50년 후에 지도가 작아지는 데 조건이 무엇인지 이해하기 어려웠다. 다른 분들을 참고했을 때, 지도의 최소 행, 최소 열로부터 최대 행, 최대 열 만큼의 지도를 출력하면 되는 문제였다.

문제 풀이

python

• 입력을 받아 map으로 2차원 리스트를 만든다.
• map[i][j] 가 땅이면 상,하,좌,우 주변이 3곳이상 바다인지 확인하고 바다라면 땅도 50년 뒤에 바다가 된다.
• map[nx][ny] 가 map 크기를 벗어난다면 바다이다
• 50년 뒤, 지도를 futureMap에 표기한다.
• 그리고 최소 행,열 최대 행,열의 위치를 x1,y1,x2,y2에 기록하고 해당 범위만 출력한다.

# 현재의 지도에서 50년 후의 지도 모습을 출력
# (상,하,좌,우)인접한 세칸 또는 네칸에 바다가 있는 섬은 바다가 된다.
# 주어지는 map 범위를 초과하는 칸은 모두 바다이다.
# 섬은 적어도 한개있다.
import copy # 얕은 복사...✨
r, c = map(int, input().split())
map = []
for i in range(r) :
    map.append(list(input()))

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

futureMap = copy.deepcopy(map)

# 50년 뒤 사라지는 땅 기록
for i in range(r):
    for j in range(c) :
        if map[i][j] == 'X' :
            cnt = 0
            for k in range(4) :
                nx = i + dx[k]
                ny = j + dy[k]
                
                if nx < 0 or ny < 0 or nx >= r or ny >= c : # 지도영역 초과하면 바다임
                    cnt += 1
                    continue
                else : 
                    if map[nx][ny] == '.' : 
                        cnt += 1
                    
            # 만일 50년뒤에 사라지는 땅이라면?
            if cnt >= 3 : futureMap[i][j] = '.'

# 지도의 크기를 줄인다.. =>? 
# -> 아이디어 : 행과 열 각각 1의 위치의 최소, 최대 구한다.
x1, y1, x2, y2 = int(1e9), int(1e9), 0, 0

for i in range(r) :
    for j in range(c) :
        if futureMap[i][j] != '.' :
            x1 = min(i,x1)
            y1 = min(j,y1)
            x2 = max(i,x2)
            y2 = max(j,y2)

for i in range(x1, x2+1) :
    for j in range(y1, y2+1) :
        print(futureMap[i][j], end="")
    print()

 

얕은 복사 vs 깊은 복사

얕은 복사	깊은 복사
최상위 객체는 복사되지만, 하위 객체들은 참조가 복사됩니다.	독립적인 객체가 생성되므로, 복사된 객체와 원본 객체는 서로 전혀 영향을 주지 않습니다.
futureMap = copy.copy(map) or futureMap = map[:]	futureMap = copy.deepcopy(map)