[소프티어 Lv3] 8단 변속기

[소프티어 Lv3] 8단 변속기

 

https://softeer.ai/practice/6283

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

[내 풀이]

- 단순하게 생각해도 되는 순수 조건문 문제였다.

- 정답률이 70%라고 해서 함정이 있는 줄 알았는데... 아니었다. (이게 왜 lv3이지?)

import sys
ipt = list(map(int, sys.stdin.readline().split(' ')))

ascList = [1, 2, 3, 4, 5, 6, 7, 8]
desList = ascList[::-1]

if ipt == ascList:
  print('ascending')
elif ipt == desList:
  print('descending')
else:
  print('mixed')

 

 

---

[소프티어 Lv3] [HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기

 

https://softeer.ai/practice/6283

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

[내 풀이]

- 도착만 체크하는 것이 아니라 경로가 중요하므로 bfs가 아닌 dfs를 사용해야 한다.

- 순서대로 방문을 체크하는 방법이 핵심이었던 문제. 순서대로 방문을 하지 못한 경우, 그 이후의 경로탐색을 중단해야 한다(return 이 아니라 continue....).

 

* 순서대로 방문을 하지 못한 것 : 

방문 리스트 안의 값인데 현재 당장 방문해야 되는 노드가 아닌 경우이다.

이 경우 순서가 꼬였다고 판단한다. 

 

[내 풀이 수정 과정]

잔 실수가 있어서 한참 수정했다... 수정 과정은 너무 길어서 접어둔다. 

초기 코드 

- 자꾸 마지막 정답 위치가 1에서 바뀌지 않는 문제가 있었다.

- 끝나고는 도착 위치인 (1,2 )는 0으로 바뀌어야 하는데 바뀌지 않았다.

import sys

n, m = map(int, sys.stdin.readline().split())
mtx = []
for i in range(n):
  mtx.append(list(map(int, sys.stdin.readline().split())))
todo = []
for i in range(m):
  x, y = map(int, sys.stdin.readline().split())
  todo.append([x-1, y-1])

for row in mtx:
  print(row)
print(todo)

visited = [[0]*m for _ in range(m)]
for row in visited:
  print(row)

def dfs(lst, k):
  for row in visited:
    print(row)
  global cnt
  if k == m:
    print('success')
    visited[1][2] = 0
    cnt += 1
  else:
    x, y = lst
    print(x,y,k)
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
  
      if 0<=nx<n and 0<=ny<n:
        if visited[nx][ny] == 0 and mtx[nx][ny]==0:
          visited[nx][ny] = 1
          if [nx,ny] in todo and [nx,ny] != todo[k]:
            return
          if [nx, ny] == todo[k]:
            dfs([nx,ny], k+1)
            visited[nx][ny] = 0
          else:
            dfs([nx,ny], k)
            visited[nx][ny] = 0
  

start = todo[0]
visited[start[0]][start[1]] = 1
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
cnt = 0

dfs(start, 1)
print(cnt)

 

(1,2)에 1이 남아있다.

1차 시도:

- for문으로 4방향을 체크해야 되는데, return 을 해버려서 4방향을 모두 체크하지 못했다. 이 경우는 continue를 사용했어야 했다. 

import sys

n, m = map(int, sys.stdin.readline().split())
mtx = []
for i in range(n):
  mtx.append(list(map(int, sys.stdin.readline().split())))
todo = []
for i in range(m):
  x, y = map(int, sys.stdin.readline().split())
  todo.append([x-1, y-1])

visited = [[0]*m for _ in range(m)]

def dfs(lst, k):
  global cnt
  if k == m:
    visited[1][2] = 0
    cnt += 1
  else:
    x, y = lst
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<n:
        if visited[nx][ny] == 0 and mtx[nx][ny]==0:
          if [nx,ny] in todo and [nx,ny] != todo[k]:
            continue # 이 부분에서 for 문 4 방향 돌아야 되는데, return을 해버렸던 문제 수정
          visited[nx][ny] = 1
          if [nx, ny] == todo[k]:
            dfs([nx,ny], k+1)
          else:
            dfs([nx,ny], k)
          visited[nx][ny] = 0

# 초기값
start = todo[0]
visited[start[0]][start[1]] = 1
cnt = 0

# 상수
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

dfs(start, 1)
print(cnt)

2차 시도: 

- 공개 테케는 맞았는데, 히든 테케는 맞추지 못했다. 

- 1차 시도에서 왜 (1,2)의 1이 안 사라지지 하면서 임시로 값을 하드 코딩해놨던 걸 삭제하지 않아서 발생했던 문제, 이렇게 임시로 값을 수정할 경우 # 주석을 표기해둬서, 실수를 방지할 수 있도록 대비해두자

# 11:08~ 12:10
# 순서대로 방문을 체크하는 방법: 이 핵심 

import sys

n, m = map(int, sys.stdin.readline().split())
mtx = []
for i in range(n):
  mtx.append(list(map(int, sys.stdin.readline().split())))
todo = []
for i in range(m):
  x, y = map(int, sys.stdin.readline().split())
  todo.append([x-1, y-1])

visited = [[0]*m for _ in range(m)]

def dfs(lst, k):
  global cnt
  if k == m:
  	#visited[1][2] = 0 #원인 찾으려고 임시로 값 넣어놓은 것 삭제해놓지 않았던 실수
    cnt += 1
  else:
    x, y = lst
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<n:
        if visited[nx][ny] == 0 and mtx[nx][ny]==0:
          if [nx,ny] in todo and [nx,ny] != todo[k]:
            continue
          visited[nx][ny] = 1
          if [nx, ny] == todo[k]:
            dfs([nx,ny], k+1)
          else:
            dfs([nx,ny], k)
          visited[nx][ny] = 0

# 초기값
start = todo[0]
visited[start[0]][start[1]] = 1
cnt = 0

# 상수
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

dfs(start, 1)
print(cnt)

3차 시도: 

- visited를 n으로 해야 하는데... m으로... 난 바보다... 

# visited = [[0]*m for _ in range(m)]
visited = [[0]*n for _ in range(n)]

- 이걸 수정하니 제대로 작동했다. 

 

최종 코드

import sys

n, m = map(int, sys.stdin.readline().split())
mtx = []
for i in range(n):
  mtx.append(list(map(int, sys.stdin.readline().split())))
todo = []
for i in range(m):
  x, y = map(int, sys.stdin.readline().split())
  todo.append([x-1, y-1])

visited = [[0]*n for _ in range(n)]

def dfs(lst, k):
  global cnt
  if k == m:
    cnt += 1
  else:
    x, y = lst
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<n:
        if visited[nx][ny] == 0 and mtx[nx][ny]==0:
          if [nx,ny] in todo and [nx,ny] != todo[k]:
            continue
          visited[nx][ny] = 1
          if [nx, ny] == todo[k]:
            dfs([nx,ny], k+1)
          else:
            dfs([nx,ny], k)
          visited[nx][ny] = 0

# 초기값
start = todo[0]
visited[start[0]][start[1]] = 1
cnt = 0

# 상수
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

dfs(start, 1)
print(cnt)