용답노트

알게 된 내용

• deque는 O(1) 로 맨앞에 요소를 추가할 수 있다. q.appendleft(x)
• deque는 정렬기능이 없다. 정렬 불가임.
• 빈 리스트는 list.sort() 동작하지 않는다. a = sorted(list) 이런식으로 써야함.

A = []
B = deque(A.sort()) #불가능
B = deque(sorted(A)) #가능

오답노트

• 문제가 길고 조건이 많아서, 자칫해서 문제를 잘못이해하면 몇시간을 통째로 날릴 수 있음. 코드 작성 전에 아래와 같이 조건을 잘 정리해 두었던 것이 도움이 되었음

#봄: 나이만큼 양분 먹고 / 나이 1 증가 / 여러 나무가 있으면 어린나무부터 양분먹기 / 양분없으면 사망 
#여름: 죽은나무 나이 나누기2 만큼 양분추가(소수점 버림)
#가을: 5의 배수 나이인 경우 나무 번식 / 인접한 8개 칸에 나이 1인 나무 생성
#겨울: 주어진 양분 배급

• 8방향 이동을 r, c 가 0일 때와 n-1 일때 조건을 세워서 풀었음. -> 아래와 같이 작성하면 가독성도 좋고 실수할 가능성도 낮음.

#이동
dx=[-1, 0, 1,-1, 1,-1, 0, 1]
dy=[-1,-1,-1, 0, 0, 1, 1, 1]

for i in range(8):
    nx=r+dx[i]
    ny=c+dy[i]
    if 0<=nx<n and 0<=ny<n:
        tree[nx][ny].appendleft(1)

코드

import sys
from collections import deque
sys.stdin = open("input.txt", "r") 

n, m, k = map(int,sys.stdin.readline().split())
A=[False for _ in range(n)]
for _ in range(n):
    A[_]=list(map(int,sys.stdin.readline().split()))

#현재 양분 값 저장하는 배열
B=[[5 for i in range(n)] for j in range(n)]

#트리 배열 생성
#트리 배열 각 노드의 값 == [1나무의 나이,2나무의 나이,..., x나무의 나이]
tree=[[[] for c in range(n)] for r in range(n)]
for _ in range(m):
    x,y,z = map(int,sys.stdin.readline().split())
    tree[x-1][y-1].append(z)

#처음 한번만 정렬
for i in range(n):
    for j in range(n):
        tree[i][j] = deque(sorted(tree[i][j]))
#이동
dx=[-1, 0, 1,-1, 1,-1, 0, 1]
dy=[-1,-1,-1, 0, 0, 1, 1, 1]

for y in range(k):
    sons=[] #번식하는 나무 담아둘 곳.
    for r in range(n):
        for c in range(n):
            cnt_tree = len(tree[r][c]) #현재 땅의 나무 개수 체크
            if cnt_tree ==0:
                B[r][c]+=A[r][c]
                continue
            #봄
            tmp=deque()
            die=0
            for age in tree[r][c]:
                if age > B[r][c]:# 잔여 양분 체크
                    die+= age//2 #죽은나무 나이 나누기2만큼 양분추가(소수점 버림)
                    continue
                B[r][c]-=age
                tmp.append(age+1)
            tree[r][c]=tmp

            #여름
            B[r][c] += die 
            
            #가을
            for t in tree[r][c]:
                if t%5 == 0: sons.append((r,c))
            #겨울
            B[r][c]+=A[r][c]
    #가을 적용
    for son in sons:
        (r,c) = son
        for i in range(8):
            nx=r+dx[i]
            ny=c+dy[i]
            if 0<=nx<n and 0<=ny<n:
                tree[nx][ny].appendleft(1)
#나무 개수 카운트
ans =0
for i in range(n):
    for j in range(n):
        ans += len(tree[i][j])
print(ans)

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

문제

• 인접한 노드(모눈종이 빈칸)들을 하나의 '뭉치'라고 했을 때, 몇개의 뭉치가 있는지 세고 각 뭉치의 넓이를 계산하는 문제.
• 백준 1012번 유기농배추와 유사한 문제(참고: https://yong-bro.tistory.com/30)
  • 단, 유기농 배추 문제와 비교했을 때 1)graph의 위 아래가 뒤집혀 있고 2)노드가 모서리 기준이므로 인덱스 계산시에 주의해야 함

오답노트

• x,y 좌표계와 행렬은 반대로 생각해야함. y가 행과 비슷한 성질이므로 행과 열은 좌표계에 올리면 y,x임.
• 좌표로 제시된 이 문제를 코드로 작성하니 결국 graph[y][x] = 1 와 같이 거꾸로 써줘야함. (아니면 애초에 행렬 좌표계로 바꿔서 생각하던가)

답안

• 주어진 사각형 정보를 활용하여 Graph 만들기
  • 인덱스가 직사각형 안에 들어오면 벽 세우기(graph[y][x] = 1)
• BFS 진행
  • 벽이 아닌것중에 방문안한곳 발견
    • cnt  +1
    • 인접한 노드 모두 방문처리. 방문처리 될 때 넓이 1 추가

import sys
import collections 

sys.stdin=open("input.txt","rt") 
m, n, k =  map(int,sys.stdin.readline().split())
graph = [[0]*n for _ in range(m)] # m행 n열
visited = [[0]*n for _ in range(m)]

for _ in range(k):
    x1,y1,x2,y2 = map(int,sys.stdin.readline().split()) #사각형 정보 입력
    for x in range(n):
        for y in range(m):
            if x>= x1 and x<= x2-1 and y >= y1 and y <= y2-1 :
                graph[y][x] =1  # 행/열을 좌표계로 올리면 y,x 꼴이 된다.
cnt =0    
dx =[1,0,-1,0]
dy =[0,1,0,-1]
q = collections.deque()
a = []
for i in range(m): #여기부턴 행/열 좌표계 이므로 위쪽 코드와 m n 순서가 다르다.
    for j in range(n):
        if graph[i][j]==0 and visited[i][j]==0:
            cnt+=1
            visited[i][j] =1
            a.append(1)
            q.append((i,j))
            while q:
                x, y = q.popleft()                
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if nx >= 0 and nx < m and ny >= 0 and ny < n and graph[nx][ny]==0 and visited[nx][ny] ==0:
                        visited[nx][ny]=1
                        a[cnt-1] += 1
                        q.append((nx,ny))

print(cnt)
print(*sorted(a))

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

오답노트

• 문제를 자세히 읽지 않고 첫 노드에서 첫 노드까지 거리가 0이라고 생각함. 예시에서 세어보니 자기 자신의 자리를 1로 정의함. 
• 첫 노드 방문처리를 빠뜨림.
• 최종 거리를 return 할 떄 print(d+1) 해야하는데 print(d)를 하였음.

답안

import sys
import collections

n,m = map(int,sys.stdin.readline().strip().split())

graph =[]
for _ in range(n):
    tmp = list(map(int,sys.stdin.readline().strip()))
    graph.append(tmp)


answer = 0
dx = [1,0,-1,0]
dy =[0,1,0,-1]
visited =[[False]*m for _ in range(n)]
q= collections.deque()
visited[0][0]=1
q.append((0,0,1))

def bfs(x,y,d):
    global q
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx <n and ny >=0 and ny <m:
                if visited[nx][ny] == 0 and graph[nx][ny] ==1:
                    if nx == n-1 and ny == m-1:
                    	#처음에 print(d)로 해서 틀렸음.
                        print(d+1)
                        return 1
                    else:
                        visited[nx][ny]=1
                        q.append((nx,ny,d+1))


while q:
    x,y,d = q.popleft()
    if bfs(x,y,d):
        break