구현(알고리즘, Python)

구현 유형

이코테의 게임 문제
백준문제

이코테 책읽었을 때의 코드

약간 이코테 정담 아이디어를 슬쩍 보고 작성한 코드

n, m = map(int,input().split())
x, y, p = map(int, input().split())

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

grid = []
for i in range(n):
    grid.append(list(map(int, input().split())))

visited = [[False for _ in range(m)] for _ in range(n)]
visited[x][y] = True
def move(x, y, p):
    mcnt = 0
    while True:
        fcnt = 0
        for i in range(4):
            print('x,y', (x, y))
            print('i', i)
            if p == 0:
                np = 3
            else:
                np = p - 1

            nx = x + dx[np]
            ny = y + dy[np]
			
            # 맵은 어차피 벽으로 사면이 둘러쌓여 있어서 a는 사실 불필요
            a = (nx<0 or nx>(n-1) or ny<0 or ny>(m-1))
            # 방문한 격자라면
            b = (visited[nx][ny] == True)
            # 벽이라면
            c = (grid[nx][ny]==1)

            if a or b or c:
                p = np # 방향만 바꾸고
                fcnt += 1 
            else:
                x = nx
                y = ny # 위치 바꾸고
                p = np # 방향 바꾸고
                visited[x][y] = True
                mcnt += 1
                break # 옮겨갔으니까 break
        if fcnt==4:
            if grid[x-dx[p]][y-dy[p]] == 1:
                print(visited)
                return mcnt
            x -= dx[p]
            y -= dy[p]

print(move(x, y, p))

• 해당 방향으로 앞으로 갈때는 x + dx[i] 뒤로 갈때는 x - dx[i]

• 구현 문제는 문제 이해가 엄청 중요함

• 모든 경우가 어떻게 되는건지 머릿속으로 시뮬돌려봐야됌

• 백준풀고 다시보니 이코테 테스트 케이스만 통과.

• 처음 노드 방문처리하는 것 잊지 말자

• flag처리를 안해도 되는 이유는 위 코드에서는 방향만 바꾸는 횟수(fcnt)를 따로 세기 때문이다.

기억리셋되고 백준문제 푼 코드

n, m = map(int, input().split())
x, y, pos = map(int, input().split())

grid = []
for _ in range(n):
    grid.append(list(map(int,input().split())))
visited = [[False for _ in range(m)] for _ in range(n)]
cnt = 1
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
visited[x][y] = True

while True:
    for i in range(4):
        flag = False
        if pos == 0:
            pos = 3
        else:
            pos -= 1

        nx = x + dx[pos]
        ny = y + dy[pos]
		
        # 움직일 수 있는 조건이라면
        if grid[nx][ny] != 1 and visited[nx][ny]!=True:
            visited[nx][ny] = True
            x = nx
            y = ny
            cnt += 1
            flag = True # 4번 돌았지만 위치를 옮긴 상황을 기록
            break
    if i == 3:
        if flag==True:
            continue
        elif grid[x-dx[pos]][y-dy[pos]] == 1:
            break
        else:
            x -= dx[pos]
            y -= dy[pos]
print(cnt)

• for문 4번 돌았지만 마지막 방향에서 움직일 수 있는 경우가 있기때문에 flag로 그런 상황 고려
• 처음노드 방문처리 & 처음노드고려해서 cnt 1부터 시작 주의

달팽이 문제

• 구현 문제
• 좌표만 조작해서 이동한다는 개념
• 삼각형이 아닌 nxn 어레이라고 생각하면 인덱싱할 때 더욱 쉽다는 점
• 특정방향으로 한번씩 돌때마다 그 단계의 개수는 한개씩 줄어든다는 점
• 참고

n = 5
grid = [[-1 for _ in range(n)]  for _ in range(n)]
x = -1
y = n
num = 0
for i in range(n):
    for j in range(n-i):
        if i%3==0:
            x += 1
            y -= 1
        elif i%3==1:
            x -= 1
        elif i %3 == 2:
            y += 1
        num += 1
        grid[x][y] = num

# print(grid)
for i in grid:
    print(i)

상어초등학교

문제링크

n = int(input())
num = {}
for _ in range(n**2):
    a = list(map(int, input().split()))
    num[a[0]] = a[1:]
grid = [[0 for _ in range(n)] for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in num.keys():
    # print('i', num[i][0])
    g = []
    v1 = []
    v2 = []
    if i==0:
        grid[1][1] = i
    else:
        for x in range(n):
            for y in range(n):
                if grid[x][y] == 0:
                    s = 0
                    so = 0
                    for j in range(4):
                        nx = x + dx[j]
                        ny = y + dy[j]
                        if nx < 0 or nx >(n-1) or ny<0 or ny>(n-1): # 좌표룰 벗어나지 않으면
                            continue
                        else:
                            if grid[nx][ny] in num[i]: # 친한친구면 +1
                                s += 1
                            if grid[nx][ny] == 0: # 빈자리면 +1
                                so += 1
                    g.append((x, y))
                    v1.append(s)
                    v2.append(so)

        if v1.count(max(v1)) == 1:
            x, y = g[v1.index(max(v1))]
            grid[x][y] = i
            # print('1 if', (x, y), num[i][0])
        else:
            v1_ind = []
            v2_val = []
            for p, pp in enumerate(v1):
                 if pp == max(v1):
                     v1_ind.append(p)
            for pp in v1_ind:
                v2_val.append(v2[pp])

            if v2_val.count(max(v2_val)) == 1:
                x, y = g[v1_ind[v2_val.index(max(v2_val))]]
                grid[x][y] = i
                # print('2 if', (x, y), num[i][0])
            else: # 3. 행작고 열작을수록
                x, y = g[v1_ind[v2_val.index(max(v2_val))]]
                grid[x][y] = i
                # print('2 else', (x, y), num[i][0])

all_s = 0
for x in range(n):
    for y in range(n):
        s = 0
        for ii in range(4):
            nx = x + dx[ii]
            ny = y + dy[ii]
            if nx < 0 or nx > (n - 1) or ny < 0 or ny > (n - 1):  # 좌표룰 벗어나지 않으면
                continue
            else:
                if grid[nx][ny] in num[grid[x][y]]:  # 친한친구면 +1
                    s += 1
        if s==2:
            s = 10
        elif s==3:
            s = 100
        elif s==4:
            s = 1000
        all_s += s

print(all_s)

• 구현문제는 문제를 정확히 이해하는 것이 중요
• 초기값 설정하고 max값구하는 방법도 생각해보았다. 행,열 번호가 작은 위치가 먼저 저장되는 점도 좋을 것 같았다.
• 그렇게 하면 같은 max값을 가지는 경우에 해결할 수 없을 것 같아 보류했는데 아래와 같이 풀면 해결되는 일이었다.

코드출처

import sys
from collections import defaultdict
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
N = int(input())
arr = [[0]*N for _ in range(N)]
likedict = defaultdict(list)
result = 0
 
for _ in range(N*N):
    _input = list(map(int, input().split()))
    likedict[_input[0]] = _input[1:]
    
    max_x = 0
    max_y = 0
    max_like = -1
    max_empty = -1
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 0:
                likecnt = 0
                emptycnt = 0
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0 <= nx < N and 0 <= ny < N:
                        if arr[nx][ny] in _input:
                            likecnt += 1
                        if arr[nx][ny] == 0:
                            emptycnt += 1
                            
                if max_like < likecnt or (max_like == likecnt and max_empty < emptycnt):
                    max_x = i
                    max_y = j
                    max_like = likecnt
                    max_empty = emptycnt
                    
    arr[max_x][max_y] = _input[0]
    
for i in range(N):
    for j in range(N):
        cnt = 0
        like = likedict[arr[i][j]]
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if 0 <= nx < N and 0 <= ny < N:
                if arr[nx][ny] in like:
                    cnt += 1
        if cnt != 0:
            result += 10 ** (cnt-1)
            
print(result)

• 친한친구수가 기존보다 크다면 -> 그 값으로 저장

• 친한친구수가 같다면 -> 빈자리수가 크다면 -> 그 값으로 저장

• 친한 친구수가 같다면 -> 빈자리수가 같다면 -> 그 전에 있던 값 그대로

• 모든 선호리스트 받아서 저장할 필요도 없었다.
  입력과 동시에 하면 됐음

• defaultdict(list)라는 건 키값과 value를 따로 지정하지 않았어도
  새로운 키값을 받았을 때 기본적으로 빈리스트가 value가 된다.