๐Ÿ“š
TIL
  • README
  • Git
    • Basic
    • Remote Repository
    • Log & Diff
    • Rebase&Cherri-Pick
    • git-flow
  • DevOps
    • Monolithic vs MSA
    • Jenkins ์‹œ์ž‘ํ•˜๊ธฐ
    • Airflow ์‹œ์ž‘ํ•˜๊ธฐ
    • Airflow ์‹œ์ž‘ํ•˜๊ธฐ
    • Build Tools
      • maven
  • ๊ฐœ๋ฐœ ๋ฐฉ๋ฒ•๋ก 
    • TDD
  • Spring
    • IoC
    • Is Spring Bean Thread-Safe?
    • Spring Singleton
    • Component Scan
    • Spring Annotation
    • ์˜์กด ๊ด€๊ณ„ ์ฃผ์ž…(DI)
    • Lombok ํ™œ์šฉํ•˜๊ธฐ
    • Bean ์ƒ๋ช…์ฃผ๊ธฐ์™€ ์ฝœ๋ฐฑ
    • Bean Scope
    • AOP(1) - AOP๋ž€
    • AOP(2) - Aop Proxy
    • AOP(3) - Dynamic Proxy
    • AOP(4) - AspectJ
    • POJO
    • Spring ์„œ๋น„์Šค ๊ตฌ์กฐ
    • Transaction
    • JPA๋ž€?
    • JPA Entity
    • Spring Data JPA
    • Spring Data Specification
    • Model Mapping
    • Cache
    • restTemplate
    • YAML ํŒŒ์ผ ์„ค์ •
    • Spring Boot
      • H2 DB ์„ค์ •
      • ๋‹ค์ค‘ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์„ค์ •
      • Mybatis ์—ฐ๋™ํ•˜๊ธฐ
    • Spring Batch
      • Batch ์‹œ์ž‘ํ•ด๋ณด๊ธฐ
      • Batch Job Flow
      • Job
      • Step
      • Batch Scope & Job Parameter
      • JobRepository์™€ ๋ฉ”ํƒ€ํ…Œ์ด๋ธ”
      • Chunk ์ง€ํ–ฅ ํ”„๋กœ๊ทธ๋ž˜๋ฐ
      • ItemReader
      • ItemProcessor
      • ItemWriter
      • Batch Schedular
      • Job๋ณ„ Bean๋“ฑ๋กํ•˜๊ธฐ
      • Batch ๊ตฌํ˜„์‹œ ๋ฐœ์ƒํ•œ ์˜ค๋ฅ˜ ์ •๋ฆฌ
      • Spring Batch Scaling
        • Multithread Job๊ตฌํ˜„์‹œ ์ด์Šˆ์‚ฌํ•ญ
    • Spring test
      • Junit5
        • ํ…Œ์ŠคํŠธ ์ด๋ฆ„ ํ‘œ๊ธฐ
        • ํ…Œ์ŠคํŠธ ๊ทธ๋ฃน ์‚ฌ์ด์˜ ๊ด€๊ณ„
        • ํƒœ๊ทธ์™€ ํ•„ํ„ฐ๋ง
        • ๋™์  ํ…Œ์ŠคํŠธ
        • ํ…Œ์ŠคํŠธ LifeCycle
        • ํ…Œ์ŠคํŠธ ๋ฉ”์„œ๋“œ
        • ํ…Œ์ŠคํŠธ ์ˆœ์„œ
        • AssertJ
        • ํ…Œ์ŠคํŠธ ๋ณ‘๋ ฌ ์‹คํ–‰
        • AssertJ
        • Mock
      • Spring Boot Test DB ๋ถ„๋ฆฌ
      • Spring Batch Test
  • Web Application
    • Web Server & WAS
    • ๊ด€๋ จ ๊ฐœ๋… - HTTP API, HTML, CSR, SSR
    • Servlet
    • JSP
    • Cookie And Session
    • ์˜ˆ์™ธํŽ˜์ด์ง€
    • Java Bean
    • JDBC
    • Connection Pool
    • ํŒŒ์ผ ์—…๋กœ๋“œ
    • Expression Language
    • JSTL
    • FrontControllerํŒจํ„ด Command ํŒจํ„ด
    • Forwarding
    • MVC
    • ํšŒ์›๊ฐ€์ž…์˜ˆ์ œ
    • ์ฐธ๊ณ 
      • ๊ฐœ๋ฐœํ™˜๊ฒฝ์„ค์ •
  • Java+
    • SOAP/WSDL vs REST
    • WSDL์„ JAVA๋กœ ๋ณ€ํ™˜ํ•˜๊ธฐ
    • SOAP ํ†ต์‹  OPEN API๋กœ ๊ฐœ๋ฐœํ•ด๋ณด๊ธฐ
  • Java
    • Basic
      • ๋ณ€์ˆ˜์™€ ํƒ€์ž…
      • ์—ฐ์‚ฐ์ž
      • ์กฐ๊ฑด๋ฌธ๊ณผ ๋ฐ˜๋ณต๋ฌธ
      • ์ฐธ์กฐ ํƒ€์ž…
      • ํด๋ž˜์Šค
      • ์ƒ์†(Inheritance)
      • ์ธํ„ฐํŽ˜์ด์Šค(Interface)
      • ์ค‘์ฒฉ ํด๋ž˜์Šค์™€ ์ค‘์ฒฉ ์ธํ„ฐํŽ˜์ด์Šค
      • ์˜ˆ์™ธ ์ฒ˜๋ฆฌ
      • API - Object, System, Class, Math, Wrapper
      • API - String, StringBuffer, StringBuilder
      • Thread
      • Generic
      • Lambda
      • Collection - List, Set
      • Collection - Map
      • Collection - Tree
      • Collection - Stack, Queue
      • Stream
      • Reflection
      • ์ •๊ทœํ‘œํ˜„์‹
      • GUI
      • UML
      • Serializable
    • Advanced
      • OutOfMemoryError
      • AutoValue
      • meta-annotation
        • @Retention
        • @Target
        • @Repeatable
    • Effective Java 3/E
      • ITEM 1: Static Factory Method(์ •์  ๋ฉ”์†Œ๋“œ)
      • ITEM 2: Builder Pattern
      • ITEM 3: Singleton
      • ITEM 4: Private Constructor
      • ITEM 5: Dependency Injection
      • ITEM 6: Avoid Unnecessary Object
      • ITEM 7: Eliminate Object Reference
      • ITEM 8: Avoid finalizer and cleaner
      • ITEM 9: try-with-resources
      • ITEM 10: The gerneral contract when overriding equlas
      • ITEM 11: Overriding hashCode
      • ITEM 12: overriding toString
      • ITEM 13: overriding clone judiciously
      • ITEM 14: Consider implementing comparable
      • ITEM 15: ํด๋ž˜์Šค์™€ ๋ฉค๋ฒ„์˜ ์ ‘๊ทผ์„ ์ตœ์†Œํ™”ํ•ด๋ผ
      • ITEM 16: Use Accessor methods
      • ITEM 17: ๋ณ€๊ฒฝ ๊ฐ€๋Šฅ์„ฑ์„ ์ตœ์†Œํ™”ํ•ด๋ผ(๋ถˆ๋ณ€ ํด๋ž˜์Šค)
      • ITEM 18: ์ƒ์†๋ณด๋‹จ ์ปดํฌ์ง€์…˜์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 19: ์ƒ์†์„ ๊ณ ๋ คํ•ด ์„ค๊ณ„ํ•˜๊ณ  ๋ฌธ์„œํ™”ํ•ด๋ผ
      • ITEM 20: ์ถ”์ƒ ํด๋ž˜์Šค๋ณด๋‹ค ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์šฐ์„ ํ•˜๋ผ
      • ITEM 21: ์ธํ„ฐํŽ˜์ด์Šค๋Š” ๊ตฌํ˜„ํ•˜๋Š” ์ชฝ์„ ์ƒ๊ฐํ•ด ์„ค๊ณ„ํ•ด๋ผ.
      • ITEM 22: ์ธํ„ฐํŽ˜์ด์Šค๋Š” ํƒ€์ž…์„ ์ •์˜ํ•˜๋Š” ์šฉ๋„๋กœ๋งŒ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 23: ํƒœ๊ทธ ๋‹ฌ๋ฆฐ ํด๋ž˜์Šค๋ณด๋‹ค ํด๋ž˜์Šค ๊ณ„์ธต๊ตฌ์กฐ๋ฅผ ํ™œ์šฉํ•ด๋ผ
      • ITEM 24: ๋ฉค๋ฒ„ ํด๋ž˜์Šค๋Š” ๋˜๋„๋ก static์œผ๋กœ ๊ตฌํ˜„ํ•ด๋ผ
      • ITEM 25: ํ†ฑ๋ ˆ๋ฒจ ํด๋ž˜์Šค๋Š” ํ•œ ํŒŒ์ผ์— ํ•˜๋‚˜๋งŒ ์ƒ์„ฑํ•ด๋ผ.
      • ITEM 26: Raw type์€ ์‚ฌ์šฉํ•˜์ง€ ๋งˆ๋ผ
      • ITEM 27: ๋น„๊ฒ€์‚ฌ ๊ฒฝ๊ณ ๋ฅผ ์ œ๊ฑฐํ•ด๋ผ
      • ITEM 28: ๋ฐฐ์—ด๋ณด๋‹ค๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 29: ์ด์™•์ด๋ฉด ์ œ๋„ค๋ฆญ ํƒ€์ž…์œผ๋กœ ๋งŒ๋“ค์–ด๋ผ
      • ITEM 30: ์ด์™•์ด๋ฉด ์ œ๋„ค๋ฆญ ๋ฉ”์„œ๋“œ๋กœ ๋งŒ๋“ค์–ด๋ผ
      • ITEM 31 : ํ•œ์ •์  ์™€์ผ๋“œ์นด๋“œ๋ฅผ ์‚ฌ์šฉํ•ด API ์œ ์—ฐ์„ฑ์„ ๋†’์—ฌ๋ผ
      • ITEM 32: ์ œ๋„ค๋ฆญ๊ณผ ๊ฐ€๋ณ€์ธ์ˆ˜๋ฅผ ํ•จ๊ป˜ ์“ธ ๋•Œ๋Š” ์‹ ์ค‘ํ•ด๋ผ
      • ITEM 33: ํƒ€์ž… ์•ˆ์ „ ์ด์ข… ์ปจํ…Œ์ด๋„ˆ๋ฅผ ๊ณ ๋ คํ•ด๋ผ
      • ITEM 34: int ์ƒ์ˆ˜ ๋Œ€์‹  ์—ด๊ฑฐ ํƒ€์ž…์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 35: ordinal ๋ฉ”์„œ๋“œ ๋Œ€์‹  ์ธ์Šคํ„ด์Šค ํ•„๋“œ๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 36: ๋น„ํŠธ ํ•„๋“œ ๋Œ€์‹  EnumSet์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 37: ordinal ์ธ๋ฑ์‹ฑ ๋Œ€์‹  EnumMap์„ ์‚ฌ์šฉํ•ด๋ผ
      • TEM 38 : ํ™•์žฅํ•  ์ˆ˜ ์žˆ๋Š” ์—ด๊ฑฐํƒ€์ž…์ด ํ•„์š”ํ•˜๋ฉด ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 39: ๋ช…๋ช… ํŒจํ„ด๋ณด๋‹ค ์• ๋„ˆํ…Œ์ด์…˜์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 40: @Override ์–ด๋…ธํ…Œ์ด์…˜์„ ์ผ๊ด€๋˜๊ฒŒ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 41: ์ •์˜ํ•˜๋ ค๋Š” ๊ฒƒ์ด ํƒ€์ž…์ด๋ผ๋ฉด ๋งˆ์ปค ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 42: ์ต๋ช… ํด๋ž˜์Šค๋ณด๋‹ค๋Š” ๋žŒ๋‹ค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 43: ๋žŒ๋‹ค๋ณด๋‹ค๋Š” ๋ฉ”์„œ๋“œ ์ฐธ์กฐ๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 44: ํ‘œ์ค€ ํ•จ์ˆ˜ํ˜• ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 45: ์ŠคํŠธ๋ฆผ์€ ์ฃผ์˜ํ•ด์„œ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 46: ์ŠคํŠธ๋ฆผ์—์„œ ๋ถ€์ž‘์šฉ ์—†๋Š” ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 47: ๋ฐ˜ํ™˜ ํƒ€์ž…์œผ๋กœ๋Š” ์ŠคํŠธ๋ฆผ๋ณด๋‹ค ์ปฌ๋ ‰์…˜์ด ๋‚ซ๋‹ค.
      • ITEM 48: ์ŠคํŠธ๋ฆผ ๋ณ‘๋ ฌํ™”๋Š” ์ฃผ์˜ํ•ด์„œ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 49: ๋งค๊ฐœ๋ณ€์ˆ˜๊ฐ€ ์œ ํšจํ•œ์ง€ ๊ฒ€์‚ฌํ•ด๋ผ
      • ITEM 50: ์ ์‹œ์— ๋ฐฉ์–ด์  ๋ณต์‚ฌ๋ณธ์„ ๋งŒ๋“ค์–ด๋ผ
      • ITEM 51: ๋ฉ”์„œ๋“œ ์‹œ๊ทธ๋‹ˆ์ฒ˜๋ฅผ ์‹ ์ค‘ํžˆ ์„ค๊ณ„ํ•ด๋ผ
      • ITEM 52: ๋‹ค์ค‘์ •์˜๋Š” ์‹ ์ค‘ํžˆ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 53: ๊ฐ€๋ณ€์ธ์ˆ˜๋Š” ์‹ ์ค‘ํžˆ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 54: null์ด ์•„๋‹Œ, ๋นˆ ์ปฌ๋ ‰์…˜์ด๋‚˜ ๋ฐฐ์—ด์„ ๋ฐ˜ํ™˜ํ•ด๋ผ
      • ITEM 55: Optional ๋ฐ˜ํ™˜์€ ์‹ ์ค‘ํ•˜๊ฒŒ ํ•ด๋ผ
      • ITEM 56: ๊ณต๊ฐœ๋œ API ์š”์†Œ์—๋Š” ํ•ญ์ƒ ์ฃผ์„์„ ์ž‘์„ฑํ•ด๋ผ
      • ITEM 57: ์ง€์—ญ๋ณ€์ˆ˜์˜ ๋ฒ”์œ„๋ฅผ ์ตœ์†Œํ™”ํ•ด๋ผ
      • ITEM 58: ์ „ํ†ต์ ์ธ for ๋ฌธ๋ณด๋‹ค๋Š” for-each๋ฌธ์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 59: ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์ตํžˆ๊ณ  ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 60: ์ •ํ™•ํ•œ ๋‹ต์ด ํ•„์š”ํ•˜๋‹ค๋ฉด float์™€ double์€ ํ”ผํ•ด๋ผ
      • ITEM 61: ๋ฐ•์‹ฑ๋œ ๊ธฐ๋ณธ ํƒ€์ž…๋ณด๋‹ค๋Š” ๊ธฐ๋ณธ ํƒ€์ž…์„ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 62: ๋‹ค๋ฅธ ํƒ€์ž…์ด ์ ์ ˆํ•˜๋‹ค๋ฉด ๋ฌธ์ž์—ด ์‚ฌ์šฉ์„ ํ”ผํ•ด๋ผ
      • ITEM 63: ๋ฌธ์ž์—ด ์—ฐ๊ฒฐ์€ ๋А๋ฆฌ๋‹ˆ ์ฃผ์˜ํ•ด๋ผ
      • ITEM 64: ๊ฐ์ฒด๋Š” ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด ์ฐธ์กฐํ•ด๋ผ
      • ITEM 65: ๋ฆฌํ”Œ๋ ‰์…˜๋ณด๋‹ค๋Š” ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 66: ๋„ค์ดํ‹ฐ๋ธŒ ๋ฉ”์„œ๋“œ๋Š” ์‹ ์ค‘ํžˆ ์‚ฌ์šฉํ•ด๋ผ
      • ITEM 67: ์ตœ์ ํ™”๋Š” ์‹ ์ค‘ํžˆ ํ•ด๋ผ
      • ITEM 68: ์ผ๋ฐ˜์ ์œผ๋กœ ํ†ต์šฉ๋˜๋Š” ๋ช…๋ช… ๊ทœ์น™์„ ๋”ฐ๋ผ๋ผ
    • ๊ฐ์ฒด์ง€ํ–ฅ ์„ค๊ณ„ ์›์น™(SOLID)
    • ๋””์ž์ธํŒจํ„ด
      • Strategy Pattern
      • Template Method Pattern
      • Factory Method Pattern
      • Singleton
      • Delegation
      • Proxy
      • Adapter Pattern
    • ์‹ค์Šต
      • ์ธํ„ฐํŽ˜์ด์Šค ์‹ค์Šต - Vehicle
      • ์ธํ„ฐํŽ˜์ด์Šค ์‹ค์Šต - Remote
      • GUI ์‹ค์Šต - Calculator
      • GUI ์‹ค์Šต - button
      • GUI ์‹ค์Šต - lotto
      • Thread ์‹ค์Šต - ์ขŒ์„์˜ˆ์•ฝ, ๋ฉ”์„ธ์ง€๋ณด๋‚ด๊ธฐ
    • Jar vs War
  • ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค
    • KEY
    • Index
    • Transaction
    • Trigger
    • Procedure / Function
    • Package
    • ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ๋ฐฐ์›€ํ„ฐ
      • ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์‹œ์Šคํ…œ
      • ๊ด€๊ณ„๋ฐ์ดํ„ฐ ๋ชจ๋ธ
      • ๊ด€๊ณ„๋Œ€์ˆ˜์™€ SQL
    • MySQL
      • Database๋ž€
      • MySQL ์‹œ์ž‘ํ•˜๊ธฐ
      • MySQL Database
      • MySQL Table
      • CRUD
      • ๊ด€๊ณ„ํ˜• ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค
      • Server์™€ Client
    • PostgreSQL
    • NoSQL
      • Install Cassandra on mac
      • Cassandra๋ž€?
      • NiFi๋ž€
  • Algorithm
    • String
    • Recursion
    • Dynamic Programming
    • Array, Struct, Pointer
    • Math
    • Sort
    • List
    • Stack
    • Queue
    • Graph
    • Tree
    • Maze
    • AVL
    • ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ(Binary Search Tree)
    • DFS์™€ BFS
    • ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜(Dijkstra's Algorithm)
    • Red-Black ํŠธ๋ฆฌ
    • A* ์•Œ๊ณ ๋ฆฌ์ฆ˜
    • Heap
    • Huffman Coding
    • Priority Queue
    • Bellman-Ford ์•Œ๊ณ ๋ฆฌ์ฆ˜
    • C++
      • Class
      • STL
        • STL pair
        • STL Container - Associate Container
        • STL Container - Sequence Container
        • STL Container - Container Adapter
  • JavaScript
    • JABASCRIPT BASIC
    • Shallow Copy vs Deep Copy
    • OBJECT MODEL
    • NODE
    • ๋™๊ธฐ ์ฒ˜๋ฆฌ vs ๋น„๋™๊ธฐ ์ฒ˜๋ฆฌ
    • AJAX
    • CALLBACK
    • PROMISE
    • DEFERRER
    • UNDERSCORE
    • WEBPACK
    • SCOPE
    • EXECUTION CONTEXT
    • Image Object
    • BFCache๋ž€?
    • history.scrollRestoration
    • Intersection Observer
    • JWT - JSON Web Token
    • HTML vs JSON
  • Vue.js
    • ํ™˜๊ฒฝ์„ค์ •
    • Vue.js๋ž€?
    • Vue Instance
    • Vue Component
    • Vue Router
    • HTTP ํ†ต์‹ 
    • Template
    • Single File Component
    • Vue Animation
    • Vuex
    • Djnago์™€ ์—ฐ๋™ํ•˜๊ธฐ
  • Backbone.js
    • Model
    • Collection
    • Sync
    • view
  • Node.js
    • Doit! - ๋…ธ๋“œ๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋Œ€ํ‘œ์ ์ธ ์„œ๋ฒ„์™€ ์šฉ๋„
    • Doit! - ๋…ธ๋“œ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ณ  ๊ฐœ๋ฐœ ๋„๊ตฌ ์„ค์น˜ํ•˜๊ธฐ
    • Doit! - ๋…ธ๋“œ ๊ฐ„๋‹จํ•˜๊ฒŒ ์‚ดํŽด๋ณด๊ธฐ
    • Doit! - ๋…ธ๋“œ์˜ ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ์™€ ์นœํ•ด์ง€๊ธฐ
    • Doit! - ๋…ธ๋“œ์˜ ๊ธฐ๋ณธ ๊ธฐ๋Šฅ ์•Œ์•„๋ณด๊ธฐ
    • Doit! - ์›น ์„œ๋ฒ„ ๋งŒ๋“ค๊ธฐ
    • Doit! - ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์‚ฌ์šฉํ•˜๊ธฐ
    • Doit! - ์ต์Šคํ”„๋ ˆ์Šค ํ”„๋กœ์ ํŠธ๋ฅผ ๋ชจ๋“ˆํ™”ํ•˜๊ธฐ
    • Doit! - ๋ทฐ ํ…œํ”Œ๋ฆฟ ์ ์šฉํ•˜๊ธฐ
    • Doit! - ํŒจ์ŠคํฌํŠธ๋กœ ์‚ฌ์šฉ์ž ์ธ์ฆํ•˜๊ธฐ
    • Doit! - ์ฑ„ํŒ…์„œ๋ฒ„ ๋งŒ๋“ค๊ธฐ
    • Doit! - JSON-RPC ์„œ๋ฒ„ ๋งŒ๋“ค๊ธฐ
  • Python
    • Warning-Could not import the lzma module
    • Pandas
      • Pandas ์ž๋ฃŒ๊ตฌ์กฐ
      • Pandas ๋ฐ์ดํ„ฐ ์ž…์ถœ๋ ฅ
      • DataFrame Data ์‚ดํŽด๋ณด๊ธฐ
      • ์‹œ๊ฐํ™” ๋„๊ตฌ - Matplotlib
  • ML
    • ์ถ”์ฒœ ์‹œ์Šคํ…œ
      • Collaborative Filtering
      • Matrix Factorization
  • Django
    • Basic
      • ํ™˜๊ฒฝ์„ค์ •
      • About Django
      • Start Django Project
      • Secret Key ๊ด€๋ฆฌํ•˜๊ธฐ
      • Settings ๋ถ„๋ฆฌํ•˜๊ธฐ
      • Django App
      • Django View & URL (1)
      • Django Model
        • MySQL ์—ฐ๋™
      • Django Admin
      • Django View & URL (2)
      • Django Template
      • Django Template & View & URL
      • Django Static
      • Django form
    • Advanced
      • Django Generic View
      • Django Automated Testing
      • Django Extenstion Template
      • Django Model Package
      • Django OpenSSL setting
    • REST framework
      • Rest API
      • Serializers
      • ViewSet
    • Error
      • ํ™˜๊ฒฝ์„ค์ • zlib ์˜ค๋ฅ˜๋ฐœ์ƒ
      • ModuleNotFoundError
    • ํŒจํ‚ค์ง€
      • django-debug-toolbar
    • Vue.js ์—ฐ๋™ํ•˜๊ธฐ
  • Ruby
    • variable & input/output
    • ์กฐ๊ฑด๋ฌธ
    • ๋ฐ˜๋ณต๋ฌธ
    • Array & Hash
    • Method
    • Proc&Lamda
    • Class
  • Ruby on Rails
    • Scaffolding
    • Controller
    • Model
    • Model-M:N relation
    • Model Validation
    • ๋ฉ‹์‚ฌ 10์ฃผ์ฐจ ์ˆ˜์—…(Tip)
  • HTML/CSS
    • Udacity - Intro to HTML/CSS
    • Udacity - Responsive Web Design
    • Udacity - Responsive Images
    • HTML Basic
    • CSS Basic
    • HTML5 Sementic Tag
    • HTML ํ…์ŠคํŠธ ๊ด€๋ จ ํƒœ๊ทธ๋“ค
    • HTML5 ๋ฉ€ํ‹ฐ๋ฏธ๋””์–ด
    • HTML ํผ ๊ด€๋ จ ํƒœ๊ทธ๋“ค
    • ํ…์ŠคํŠธ ๊ด€๋ จ ์Šคํƒ€์ผ
    • ์ƒ‰์ƒ๊ณผ ๋ฐฐ๊ฒฝ์„ ์œ„ํ•œ ์Šคํƒ€์ผ
    • ๋ ˆ์ด์•„์›ƒ์„ ์œ„ํ•œ ์Šคํƒ€์ผ
    • CSS ํฌ์ง€์…”๋‹
    • ๋‹ค์žฌ๋‹ค๋Šฅํ•œ CSS3 ์„ ํƒ์ž
    • CSS์™€ ์• ๋‹ˆ๋ฉ”์ด์…˜
    • ๋ฐ˜์‘ํ˜• ์›น์ด๋ž€?
  • OS(์šด์˜์ฒด์ œ)
    • Linux
      • Daemon
      • Cron
      • ํ”„๋กœ์„ธ์Šค ๊ด€๋ จ ๋ช…๋ น์–ด
      • ํ…์ŠคํŠธ ํŒŒ์ผ ๋ช…๋ น์–ด
  • Network
    • ๋„คํŠธ์›Œํฌ ๊ธฐ๋ณธ ๊ฐœ๋…
    • ๋„คํŠธ์›Œํฌ ๊ธฐ๋ณธ ๊ทœ์น™
    • ๋ฌผ๋ฆฌ ๊ณ„์ธต
    • ๋ฐ์ดํ„ฐ ๋งํฌ ๊ณ„์ธต
    • ๋„คํŠธ์›Œํฌ ๊ณ„์ธต
    • ์ „์†ก ๊ณ„์ธต
    • ์‘์šฉ ๊ณ„์ธต
    • ๋„คํŠธ์›Œํฌ ์ „์ฒด ํ๋ฆ„
    • ๋ฌด์„  ๋žœ
  • IT ๊ธฐํƒ€์ง€์‹
    • NAS๋ž€
Powered by GitBook
On this page
  • Recursion(์ˆœํ™˜)
  • ๊ตฌํ˜„
  • Stack(DFS)
  • ๊ทœ์น™
  • C์–ธ์–ด ๊ตฌํ˜„
  • Queue(BFS)
  • ๊ทœ์น™
  • ๊ตฌํ˜„
  • Dijkstra
  • A*

Was this helpful?

  1. Algorithm

Maze

์—ฌ๋Ÿฌ๊ฐ€์ง€ ํƒ์ƒ‰๋ฐฉ๋ฒ•์„ ์ด์šฉํ•ด์„œ ๋ฏธ๋กœ์ฐพ๊ธฐ๋ฅผ ๊ตฌํ˜„ํ•ด๋ณด์•˜์Šต๋‹ˆ๋‹ค.

Recursion(์ˆœํ™˜)

๊ตฌํ˜„

#include <stdio.h>
#include "color.h"


#define MAX 10
#define PATH 0
#define WALL 1
#define BLOCKED 2  // ๋ฐฉ๋ฌธ+๊ฒฝ๋กœ์ƒ์— ์žˆ์ง€ ์•Š์€ ๊ฒƒ
#define VISITED 3  // ๋ฐฉ๋ฌธ+๊ฒฝ๋กœ๊ฐ€ ๋  ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ๋Š”๊ฒƒ

int maze[MAX+2][MAX+2]= {
    {4,4,4,4,4,4,4,4,4,4,4,4},
    {4,0,0,0,0,0,0,0,0,0,1,4},
    {4,0,1,1,0,1,1,0,1,1,1,4},
    {4,0,0,1,0,1,0,0,0,0,1,4},
    {4,0,1,0,1,0,1,1,1,0,0,4},
    {4,0,0,0,1,0,1,0,0,1,0,4},
    {4,0,1,0,1,0,0,0,1,1,0,4},
    {4,0,1,1,1,0,1,0,0,1,1,4},
    {4,0,1,0,0,0,1,1,1,0,1,4},
    {4,0,0,0,1,0,0,0,1,0,1,4},
    {4,0,1,1,1,0,1,0,0,0,0,4},
    {4,4,4,4,4,4,4,4,4,4,4,4}
};

int find_path(int x, int y){
    if(x<1 ||y<1||x>MAX||y>MAX)return 0;
    else if(maze[x][y] != PATH)return 0;
    else if(x==MAX&&y==MAX){
        maze[x][y]=VISITED;
        return 1;
    }else{
        maze[x][y] = VISITED;
        if(find_path(x-1, y)||find_path(x, y+1)||find_path(x+1, y)||find_path(x, y-1)) return 1;
        maze[x][y]=BLOCKED;
        return 0;
    }
}

int main(int argc, const char * argv[]) {
    print_maze(1, 1);
    find_path(1, 1);
    print_maze(MAX, MAX);
    return 0;
}

Stack(DFS)

stack์„ ์ด์šฉํ•ด์„œ ๋ฏธ๋กœ๋ฅผ ํ‘ธ๋Š” ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค.

๊ทœ์น™

์šฐ์„  ์ž…๊ตฌ๋Š” (1,1)์ด๋ฉฐ, ์ถœ๊ตฌ๋Š” (n-2,n-2)์ž…๋‹ˆ๋‹ค.

๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทœ์น™์œผ๋กœ ๊ธธ์„ ์ฐพ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค!

  • ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์œ„์น˜์—๋Š” ํ‘œ์‹œ๋ฅผ ํ•ด์„œ ๋ฌดํ•œ๋ฃจํ”„๋ฅผ ๋ฐฉ์ง€ํ•œ๋‹ค.

  • ํ˜„์žฌ ์œ„์น˜์—์„œ ์ผ์ •ํ•œ ๊ทœ์น™์œผ๋กœ ๋‹ค์Œ ์œ„์น˜๋กœ ์ด๋™ํ•œ๋‹ค.

    • ๋ถ, ๋™, ๋‚จ, ์„œ์˜ ์ˆœ์„œ๋กœ ๊ฒ€์‚ฌํ•ฉ๋‹ˆ๋‹ค.

    • ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ์œผ๋ฉด, ์ฆ‰, ์•„์ง ์•ˆ ๊ฐ€๋ณธ ์œ„์น˜ && ๋ฒฝ์ด ์•„๋‹ˆ๋ฉด ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ๊ฐ„๋‹ค.

  • ์•„๋ฌด ๋ฐฉํ–ฅ์œผ๋กœ๋„ ๊ฐˆ ์ˆ˜ ์—†์œผ๋ฉด ๊ทธ ์œ„์น˜์— ์˜ค๊ธฐ ์ง์ „ ์œ„์น˜๋กœ ๋˜๋Œ์•„๊ฐ„๋‹ค.

์œ„์˜ ๊ทœ์น™์„ ์ž์„ธํžˆ ์‚ดํŽด๋ณด๋ฉด

  1. ํ˜„์žฌ ์œ„์น˜๋Š” ์ถœ๋ฐœ์ ์ด๋‹ค.

  2. ๋‹ค์Œ์„ ๋ฐ˜๋ณตํ•œ๋‹ค.

    1. ํ˜„์žฌ ์œ„์น˜์— ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋Š” ํ‘œ์‹œ๋ฅผ ํ•œ๋‹ค.(๋…ธ๋ž€์ƒ‰)

    2. ํ˜„์žฌ ์œ„์น˜๊ฐ€ ์ถœ๊ตฌ๋ผ๋ฉด ์ข…๋ฃŒํ•œ๋‹ค.

    3. ํ˜„์žฌ ์œ„์น˜์—์„œ ๋ถ, ๋™, ๋‚จ, ์„œ 4๋ฐฉํ–ฅ์— ๋Œ€ํ•ด ์ˆœ์„œ๋Œ€๋กœ

      1. ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š”์ง€(๋ฒฝ, ๋ฏธ๋กœ์˜ ์™ธ๋ถ€, ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์œ„์น˜)๊ฐ€ ์•„๋‹Œ์ง€ ๊ฒ€์‚ฌํ•œ๋‹ค.

      2. ๋งŒ์•ฝ ๊ฐˆ ์ˆ˜ ์žˆ์œผ๋ฉด ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•œ๋‹ค.

    4. ๋งŒ์•ฝ 3๋ฒˆ์—์„œ 4๋ฐฉํ–ฅ ์ค‘ ์–ด๋А ์ชฝ์œผ๋กœ๋„ ๊ฐ€์ง€ ๋ชปํ–ˆ๋‹ค๋ฉด ํ˜„์žฌ ์œ„์น˜์— ๋„๋‹ฌํ•˜๊ธฐ ์ง์ „ ์œ„์น˜๋กœ ๋Œ์•„๊ฐ„๋‹ค.

1,2,3,4์˜ ๊ณผ์ •์„ ๋˜ํ’€์ดํ•˜์—ฌ ์ตœ์ข…์ ์œผ๋กœ ์ถœ๊ตฌ์— ๋„๋‹ฌํ•˜๋ฉด ๋ฏธ๋กœ์ฐพ๊ธฐ๋Š” ์„ฑ๊ณตํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

C์–ธ์–ด ๊ตฌํ˜„

1. ๋ฏธ๋กœ๋Š” 2์ฐจ์› ๋ฐฐ์—ด๋กœ ๊ตฌํ˜„๋œ๋‹ค. maze[x][y]
2. ํ˜„์žฌ ์œ„์น˜๋Š” ์ถœ๋ฐœ์ (1,1)์ด๋‹ค.
3. ๋‹ค์Œ์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
    ใ„ฑ. ํ˜„์žฌ ์œ„์น˜์— ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋Š” ํ‘œ์‹œ๋ฅผ ํ•œ๋‹ค.(2)
    ใ„ด. ํ˜„์žฌ ์œ„์น˜๊ฐ€ ์ถœ๊ตฌ๋ผ๋ฉด ์ข…๋ฃŒํ•œ๋‹ค. maze[n-2][n-2]
    ใ„ท. ํ˜„์žฌ ์œ„์น˜์—์„œ ๋ถ, ๋™, ๋‚จ, ์„œ 4๋ฐฉํ–ฅ์— ๋Œ€ํ•ด ์ˆœ์„œ๋Œ€๋กœ 
        - ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š”์ง€(๋ฒฝ, ๋ฏธ๋กœ์˜ ์™ธ๋ถ€, ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์œ„์น˜)๊ฐ€ ์•„๋‹Œ์ง€ ๊ฒ€์‚ฌํ•œ๋‹ค.
        - ๋งŒ์•ฝ ๊ฐˆ ์ˆ˜ ์žˆ์œผ๋ฉด ํ˜„์žฌ ์œ„์น˜๋ฅผ ์Šคํƒ์— pushํ•˜๊ณ  ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™
    ใ„น. ๋งŒ์•ฝ ใ„ท๋ฒˆ์—์„œ 4๋ฐฉํ–ฅ ์ค‘ ์–ด๋А ์ชฝ์œผ๋กœ๋„ ๊ฐ€์ง€ ๋ชปํ–ˆ๋‹ค๋ฉด  ์Šคํƒ์—์„œ popํ•œ ์œ„์น˜๋กœ ๋Œ์•„๊ฐ„๋‹ค.

Position

  • position.h

//  position.h

#ifndef position_h
#define position_h

typedef struct pos{
    int x,y;
}Position;

Position move_to(Position pos, int dir);

#endif /* position_h */
  • position.c

//  position.c
#include "position.h"
// ๋ถ๋™๋‚จ์„œ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์„ธ๋กœ๊ฐ€ X, ๊ฐ€๋กœ๊ฐ€ Y
int offset[4][2] = {
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

Position move_to(Position pos,int dir){
    Position next;
    next.x = pos.x + offset[dir][0];
    next.y = pos.y + offset[dir][1];
    return next;
}

Stack

  • stack.h

//  stack.h

#ifndef stack_h
#define stack_h

#include <stdio.h>
#include <stdlib.h>
#include "position.h"


typedef struct s{
    int dir;
    struct s * next;
}Stack;

Stack * new_node(int dir);
void init(Stack **s);
int is_empty(Stack *s);
int peak(Stack *s);
void push(Stack ** top, int dir);
void pop(Stack ** top);

#endif /* stack_h */
  • stack.c

//  stack.c

#include "stack.h"

Stack * new_node(int dir){
    Stack * new = (Stack *)malloc(sizeof(Stack));
    new->dir = dir;
    new->next=NULL;
    return new;
}
void init(Stack **s){
    *s = NULL; //์Šคํƒ์ดˆ๊ธฐํ™”
}
int is_empty(Stack *s){
    // NULL์ด๋ฉด 1(true)  ์•„๋‹ˆ๋ฉด 0(false)
    return (s==NULL);
}
int peak(Stack *s){
    if(is_empty(s))return -1;
    return s->dir;
}
void push(Stack ** top,int dir){
    Stack * new = NULL;
    if(is_empty(*top)){
        new = new_node(dir);
    }else{
        new = new_node(dir);
        new->next=*top;
    }
    (*top)=new;
}
void pop(Stack ** top){
    Stack * p = *top;

    if(is_empty(*top))return;

    *top = p->next;
    free(p);
}

Color

//  color.h

#ifndef color_h
#define color_h
#define RESET   "\033[0m"
#define BLACK   "\033[30m"      /* Black */
#define RED     "\033[31m"      /* Red */
#define GREEN   "\033[32m"      /* Green */
#define YELLOW  "\033[33m"      /* Yellow */
#define BLUE    "\033[34m"      /* Blue */
#define MAGENTA "\033[35m"      /* Magenta */
#define CYAN    "\033[36m"      /* Cyan */
#define WHITE   "\033[37m"      /* White */
#define BOLDBLACK   "\033[1m\033[30m"      /* Bold Black */
#define BOLDRED     "\033[1m\033[31m"      /* Bold Red */
#define BOLDGREEN   "\033[1m\033[32m"      /* Bold Green */
#define BOLDYELLOW  "\033[1m\033[33m"      /* Bold Yellow */
#define BOLDBLUE    "\033[1m\033[34m"      /* Bold Blue */
#define BOLDMAGENTA "\033[1m\033[35m"      /* Bold Magenta */
#define BOLDCYAN    "\033[1m\033[36m"      /* Bold Cyan */
#define BOLDWHITE   "\033[1m\033[37m"      /* Bold White */


#endif /* color_h */

Main

//  main.c

#include "stack.h"
#include "position.h"
#include "color.h"
#include <unistd.h>

#define MAX 8
#define PATH 0              // ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ
#define WALL 1              // ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์—†๋Š” ๊ธธ == ๋ฒฝ ํฐ์ƒ‰!
#define VISITED 2           // ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์œ„์น˜
#define BACKTRACKED 3       // ๋ฐฉ๋ฌธํ–ˆ๋‹ค ๋˜๋Œ์•„ ๋‚˜์˜จ ์œ„์น˜
#define EDGE 4              // ํ…Œ๋‘๋ฆฌ
#define clear() printf("\033[H\033[J")

int maze[MAX+2][MAX+2]= {
    {4,4,4,4,4,4,4,4,4,4},
    {4,0,0,0,0,0,0,0,1,4},
    {4,0,1,1,0,1,1,0,1,4},
    {4,0,0,0,1,0,0,0,1,4},
    {4,0,1,0,0,1,1,0,0,4},
    {4,0,1,1,1,0,0,1,1,4},
    {4,0,1,0,0,0,1,0,1,4},
    {4,0,0,0,1,0,0,0,1,4},
    {4,0,1,1,1,0,1,0,0,4},
    {4,4,4,4,4,4,4,4,4,4}
};
int n=MAX; // ๋ฏธ๋กœ์˜ ํฌ๊ธฐ
//void make_maze();
void print_maze();
int movable(Position pos,int dir);



int main(int argc, const char * argv[]) {

    Stack * top;
    init(&top); 
//    make_maze();

    Position cur; // ํ•ญ์ƒ ํ˜„์žฌ ์œ„์น˜๋ฅผ ํ‘œํ˜„
    cur.x=1;
    cur.y=1;

    int init_dir = 0; //ํ•œ ์œ„์น˜์— ๋„์ฐฉํ–ˆ์„ ๋•Œ ์ฒ˜์Œ์œผ๋กœ ์‹œ๋„ํ•ด ๋ณผ ์ด๋™ ๋ฐฉํ–ฅ

    while(1){
        maze[cur.x][cur.y] = VISITED;
        if(cur.x == n && cur.y == n){
            print_maze(cur.x,cur.y);
            printf("๋ฏธ๋กœ๋ฅผ ์ฐพ์•˜์Šต๋‹ˆ๋‹ค!\n");
            break;
        }

    // ๋ฐฉ๋ฌธํ–ˆ๋Š”์ง€ ๊ธฐ๋กํ•˜๋Š” ๋ณ€์ˆ˜
        int forwarded = 0;

        // ๋ถ ๋™ ์„œ ๋‚จ ์ˆœ์„œ๋Œ€๋กœ 0, 1, 2, 3
        for(int dir = init_dir; dir<4;dir++){
            if(movable(cur,dir)){ //์ด๋™๊ฐ€๋Šฅํ•œ์ง€ ๊ฒ€์‚ฌ
                push(&top,dir); // ์Šคํƒ์— ํ˜„์žฌ ์œ„์น˜ ๋Œ€์‹  ์ด๋™ํ•˜๋Š” ๋ฐฉํ–ฅ์„ push
                cur = move_to(cur,dir);
                forwarded = 1;
                init_dir = 0; //์ฒ˜์Œ ๋ฐฉ๋ฌธํ•˜๋Š” ์œ„์น˜์—์„œ๋Š” ํ•ญ์ƒ 0๋ถ€ํ„ฐ ์‹œ๋„
                break;
            }
        }
        // 4๋ฐฉํ–ฅ์ค‘ ์•„๋ฌด๊ณณ๋„ ๊ฐ€์ง€ ๋ชปํ–ˆ๋‹ค๋ฉด
        if(!forwarded){
            // ์™”๋‹ค๊ฐ€ ๋˜๋Œ์•„๊ฐ„ ๊ณณ์ž„์„ ํ‘œ์‹œ
            maze[cur.x][cur.y]=BACKTRACKED;

            //์›๋ž˜ ์ถœ๊ตฌ๊ฐ€ ์—†๋Š” ๋ฏธ๋กœ
            if(is_empty(top)){
                printf("๊ธธ์ด ์—†์Šต๋‹ˆ๋‹ค.\n");
                break;
            }
            int d = peak(top);
            pop(&top);
            // ์ด์ „ ์œ„์น˜์—์„œ ์ง€๊ธˆ ์œ„์น˜์— ์˜ฌ๋•Œ d๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ–ˆ๋‹ค๋ฉด (d+2)%4๋ฒˆ ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•˜๋ฉด๋œ๋‹ค.
            // ๋˜๋Œ์•„๊ฐ€๋Š” ๋ฐฉํ–ฅ!
            cur = move_to(cur, (d+2)%4);
            // ์œ„์น˜์—์„œ d+1๋ฒˆ๋ฐฉํ–ฅ๋ถ€ํ„ฐ ์‹œ๋„ํ•˜๋ฉด๋œ๋‹ค.
            init_dir = d+1;
            print_maze(cur.x, cur.y);
            printf("๊ธธ์ด์—†์Šต๋‹ˆ๋‹ค. ๋˜๋Œ์•„๊ฐ‘๋‹ˆ๋‹ค.\n");
        }

    }


    return 0;
}

int movable(Position pos, int dir){
    Position tmp = move_to(pos, dir);
    //1. dir๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•œ ์ขŒํ‘œ๊ฐ€ 0~n-1์ด๋‚ด์— ์žˆ์–ด์•ผํ•œ๋‹ค.
    print_maze(tmp.x,tmp.y);
    printf("maze[%d][%d]=%d\n",tmp.x,tmp.y,maze[tmp.x][tmp.y]);

    if( tmp.x<1 || tmp.x>n){
        printf("x๋ฒ”์œ„์ดˆ๊ณผ\n");
        return 0;
    }
    if(tmp.y<1||tmp.y>n+1){
        printf("y๋ฒ”์œ„์ดˆ๊ณผ\n");
        return 0;
    }
    //2. wall์ด ์•„๋‹ˆ๊ณ , ๋ฒฝ์ด์•„๋‹ˆ์–ด์•ผํ•œ๋‹ค.
    switch (maze[tmp.x][tmp.y]) {
        case 0:
            printf("๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ์ž…๋‹ˆ๋‹ค.\n");
            return 1;
        case 1:
            printf("๋ฒฝ์ž…๋‹ˆ๋‹ค. ๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.\n");
            return 0;

        case 2:
            printf("์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ๊ธธ์ž…๋‹ˆ๋‹ค. ๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.\n");
            return 0;

        case 3:
            printf("์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ๊ธธ์ž…๋‹ˆ๋‹ค. ๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.\n");
            return 0;

        default:
            return 0;
    }

}

void print_maze(int x,int y){
    sleep(1);
    clear();
    for(int i=0;i<MAX+2;i++){
        for(int j=0;j<MAX+2;j++){
            switch (maze[i][j]) {
                case 0:
                    printf(BLACK);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }

                    printf("ใ…");
                    printf(RESET);
                    break;
                case 1:
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("ใ…");
                    break;
                case 2:
                    printf(BOLDYELLOW);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("ใ…");
                    printf(RESET);
                    break;

                case 3:
                    printf(BOLDGREEN);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("ใ…");
                    printf(RESET);
                    break;
                case 4:
                    printf(BOLDBLUE);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                        printf("ใ…");
                    }else
                        printf("ใ…");
                    printf(RESET);
                    break;
                default:
                    break;
            }
            printf(RESET);
            if(j==MAX+1)printf("\n");
        }
    }
    printf(RESET);
}
  • ์Šคํƒ์„ ์ด์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ํ•œ์ชฝ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋งŒํผ ๊นŠ์ด ๊ฐ„๋ฏ€๋กœ DFS๋ฐฉ๋ฒ•์ด๋‹ค.

Queue(BFS)

๊ทœ์น™

๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ˆœ์„œ๋กœ cell๋“ค์„ ๋ฐฉ๋ฌธํ•œ๋‹ค.

  • L0 = {s}, ์—ฌ๊ธฐ์„œ s๋Š” ์ถœ๋ฐœ ์ง€์ 

  • L1 = L0์—์„œ 1๋ฒˆ์— ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์…€๋“ค

  • L2 = L1์—์„œ 1๋ฒˆ์— ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์…€๋“ค ์ค‘์— L0์— ์†ํ•˜์ง€ ์•Š๋Š” ์…€๋“ค

  • โ€ฆ

  • Ln = Ln-1์—์„œ 1๋ฒˆ์— ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์…€๋“ค ์ค‘์— Ln-2์— ์†ํ•˜์ง€ ์•Š๋Š” ์…€๋“ค

์Šคํƒ์—์„œ๋Š” ๋ถ->๋™->๋‚จ->์„œ๋กœ ์ฐพ๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ ๊ฒฝ๋กœ๋กœ ์ฐพ๋Š”์ง€ ๋ณด์žฅํ•  ์ˆ˜ ์—†๋‹ค. ํ•˜์ง€๋งŒ ํ์—์„œ๋Š” ๋™์‹ฌ์› ํ˜•ํƒœ๋กœ ์ฐพ๊ธฐ๋•Œ๋ฌธ์— ์ž…๊ตฌ์—์„œ ์ถœ๊ตฌ๊นŒ์ง€ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค.

- ํ•˜๋‚˜์˜ ํ๋ฅผ ๋งŒ๋“ ๋‹ค.
- ์œ„์น˜(0,0) ๋Š” ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์œ„์น˜์ž„์„ ํ‘œ์‹œํ•˜๊ณ , ํ์— ์œ„์น˜(0,0)์„ ๋„ฃ๋Š”๋‹ค. 
- ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ๋‹ค์Œ์„ ๋ฐ˜๋ณตํ•œ๋‹ค.
    - ํ์—์„œ ํ•˜๋‚˜์˜ ์œ„์น˜ p๋ฅผ ๊บผ๋‚ธ๋‹ค.
    - p์—์„œ ํ•œ ์นธ ๋–จ์–ด์ง„ ์œ„์น˜๋“ค ์ค‘์—์„œ ์ด๋™ ๊ฐ€๋Šฅํ•˜๋ฉด์„œ ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋ชจ๋“  ์œ„์น˜๋“ค์„ ๋ฐฉ๋ฌธ๋œ ์œ„์น˜์ž„์„ ํ‘œ์‹œํ•˜๊ณ  ํ์— ๋„ฃ๋Š”๋‹ค.
    - ๋งŒ์•ฝ ๊ทธ ์œ„์น˜๊ฐ€ ์ถœ๊ตฌ๋ผ๋ฉด ์ข…๋ฃŒํ•œ๋‹ค.

์ถœ๊ตฌ์—์„œ ์ˆซ์ž๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ๋ฐฉํ–ฅ์œผ๋กœ ๋”ฐ๋ผ๊ฐ€๋ฉด ์ž…๊ตฌ์— ๋„๋‹ฌํ•œ๋‹ค.

๊ตฌํ˜„

Position

์Šคํƒ๊ณผ ๋™์ผ

Queue

//
//  queue.h
//  maze_queue
//
//  Created by dahye Jeong on 2018. 5. 20..
//  Copyright ยฉ 2018๋…„ dahye Jeong. All rights reserved.
//

#ifndef queue_h
#define queue_h

#include <stdio.h>
#include <stdlib.h>
#include "position.h"

typedef struct node{
    Position pos;
    struct node * next;
}QNode;

typedef struct que{
    QNode *front, *rear;
}Queue;

void enQueue(Queue * q,Position pos);
void deQueue(Queue * q);
Position front(Queue *queue);
Position rear(Queue *queue);
QNode * new_node(Position pos);
Queue * creat_queue(void);

#endif /* queue_h */
//
//  queue.c
//  maze_queue
//
//  Created by dahye Jeong on 2018. 5. 20..
//  Copyright ยฉ 2018๋…„ dahye Jeong. All rights reserved.
//

#include "queue.h"

QNode * new_node(Position pos){
    QNode * new = (QNode *)malloc(sizeof(QNode));
    new->pos.x = pos.x;
    new->pos.y = pos.y;
    new->next=NULL;
    return new;
}

Queue * creat_queue(void){
    Queue * new = (Queue *)malloc(sizeof(Queue));
    new->front = new->rear= NULL;
    return new;
}


Position front(Queue *q){
    return q->front->pos;
}

Position rear(Queue *q){
    return q->rear->pos;
}

int is_empty(Queue * q){
    return (q->front==NULL && q->rear==NULL);
}

//front ํฌ์ธํ„ฐ๋Š” ์‚ญ์ œ,  rear ํฌ์ธํ„ฐ๋Š” ์‚ฝ์ž…ํ•  ๋•Œ ์‚ฌ์šฉ
void enQueue(Queue * q,Position pos){
    QNode * tmp = new_node(pos);

    if(is_empty(q)){
        q->front = q->rear = tmp;
        return;
    }
    q->rear->next= tmp;
    q->rear=tmp;
}

void deQueue(Queue * q){
    if(q->front==NULL){
        return;
    }
    q->front = q->front->next;
    if(q->front==NULL) q->rear=NULL;
}

Main

//
//  main.c
//  maze_queue
//
//  Created by dahye Jeong on 2018. 5. 20..
//  Copyright ยฉ 2018๋…„ dahye Jeong. All rights reserved.
//

#include "queue.h"
#include "position.h"
#include "color.h"
#include <unistd.h>

#define MAX 8
#define PATH 0              // ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ
#define WALL 1              // ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์—†๋Š” ๊ธธ == ๋ฒฝ ํฐ์ƒ‰!
#define EDGE 4              // ํ…Œ๋‘๋ฆฌ
#define clear() printf("\033[H\033[J")


int maze[MAX+2][MAX+2]= {
    {4,4,4,4,4,4,4,4,4,4},
    {4,0,0,0,0,0,0,0,1,4},
    {4,0,1,1,0,1,1,0,1,4},
    {4,0,0,0,1,0,0,0,1,4},
    {4,0,1,0,0,1,1,0,0,4},
    {4,0,1,1,1,0,0,1,1,4},
    {4,0,1,0,0,0,1,0,1,4},
    {4,0,0,0,1,0,0,0,1,4},
    {4,0,1,1,1,0,1,0,0,4},
    {4,4,4,4,4,4,4,4,4,4}
};

void print_maze();
int movable(Position pos,int dir);

int main(int argc, const char * argv[]) {


    Queue *q = creat_queue();

    Position cur;
    cur.x=1;
    cur.y=1;


    enQueue(q,cur);

    // ์ถ”๊ฐ€ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ธฐ ์œ„ํ•ด ๋ฐฉ๋ฌธ ํ‘œ์‹œ๋ฅผ ์Œ์ˆ˜๋กœ ์ €์žฅ
    maze[1][1]=-1;
    int found = 0;

    while(!is_empty(q)){
        Position cur = front(q);
        deQueue(q);
        for(int dir=0;dir<4;dir++){
            //๊ทธ ์…€์ด 1(๋ฒฝ)์ด ์•„๋‹ˆ๋ฉด์„œ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๊ณณ์ธ์ง€ ๊ฒ€์‚ฌ!
            if(movable(cur,dir)){
                //move_to๋„ ๋™์ผํ•œ ํ•จ์ˆ˜
                Position pos = move_to(cur,dir);
                // ์ถ”๊ฐ€ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ธฐ ์œ„ํ•ด ๋ฐฉ๋ฌธ ํ‘œ์‹œ๋ฅผ ์Œ์ˆ˜๋กœ ์ €์žฅ
                maze[pos.x][pos.y] = maze[cur.x][cur.y]-1;

                if(pos.x==MAX&&pos.y==MAX){
                    printf("๋ฏธ๋กœ๋ฅผ ์ฐพ์•˜์Šต๋‹ˆ๋‹ค.\n");
                    final_path(pos);
                    found=1;
                    exit(0);
                }
                enQueue(q,pos);
            }
        }
    }

    return 0;
}
  • movableํ•จ์ˆ˜

int movable(Position pos, int dir){
    Position tmp = move_to(pos, dir);
    //1. dir๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•œ ์ขŒํ‘œ๊ฐ€ 1~MAX์ด๋‚ด์— ์žˆ์–ด์•ผํ•œ๋‹ค.
    print_maze(tmp.x,tmp.y);
    printf("maze[%d][%d]=%d\n",tmp.x,tmp.y,maze[tmp.x][tmp.y]);

    if( tmp.x<1 || tmp.x>MAX){
        printf("x๋ฒ”์œ„์ดˆ๊ณผ\n");
        return 0;
    }
    if(tmp.y<1||tmp.y>MAX){
        printf("y๋ฒ”์œ„์ดˆ๊ณผ\n");
        return 0;
    }
    //2. wall์ด ์•„๋‹ˆ๊ณ , ๋ฒฝ์ด์•„๋‹ˆ์–ด์•ผํ•œ๋‹ค.
    switch (maze[tmp.x][tmp.y]) {
        case 0:
            printf("๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ์ž…๋‹ˆ๋‹ค.\n");
            return 1;
        case 1:
            printf("๋ฒฝ์ž…๋‹ˆ๋‹ค. ๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.\n");
            return 0;
        default:
            printf("์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ๊ธธ์ž…๋‹ˆ๋‹ค. ๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.\n");
            return 0;
    }

}
  • print_maze

void print_maze(int x,int y){
//    sleep(1);
//    clear();
    for(int i=0;i<MAX+2;i++){
        for(int j=0;j<MAX+2;j++){
            switch (maze[i][j]) {
                case 0:
                    printf(BLACK);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }

                    printf("ใ…");
                    printf(RESET);
                    break;
                case 1:
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("ใ…");
                    break;
                case 4:
                    printf(BOLDBLUE);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                        printf("ใ…");
                    }else
                        printf("ใ…");
                    printf(RESET);
                    break;
                default:
                    printf(BOLDYELLOW);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("ใ…");
                    printf(RESET);
                    break;

                    break;
            }
            printf(RESET);
            if(j==MAX+1)printf("\n");
        }
    }
    printf(RESET);
}
  • final_path

๋งˆ์ง€๋ง‰์œผ๋กœ ์ฐพ์€ ์ตœ์ข… ๊ฒฝ๋กœ๋ฅผ ํ‘œ์‹œํ•ด์ฃผ๊ธฐ ์œ„ํ•œ ํ•จ์ˆ˜์ž…๋‹ˆ๋‹ค.

void final_path(Position pos){

    Position cur = pos;
    Position next;

    int offset[4][2] = {
        {-1,0},{0,1},{1,0},{0,-1}
    };
    int num=maze[cur.x][cur.y]+1;

    maze[cur.x][cur.y]=FINAL;

    while(1){
        for(int i=0;i<4;i++){
            next.x=cur.x+offset[i][0];
            next.y=cur.y+offset[i][1];
            if(maze[next.x][next.y]==num){
                maze[next.x][next.y]=FINAL;
                cur=next;
                num++;
                break;
            }
        }
        if(cur.x==1&&cur.y==1)break;
    }
    print_maze(n-2, n-2);
}

Dijkstra

/*
์ถœ๋ฐœ์ ์œผ๋กœ ๋ถ€ํ„ฐ ๋ชจ๋“ ๋…ธ๋“œ์˜ ์ตœ๋‹จ๊ฑฐ๋ฆฌ
๋‹ค์ต์ŠคํŠธ๋ผ ์ธ์ ‘๋ฆฌ์ŠคํŠธ๋กœ ๋ฏธ๋กœ์ฐพ๊ธฐ ์ตœ๋‹จ๊ฑฐ๋ฆฌ ๊ตฌํ•จ!
*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "color.h"
#define MAX 8
#define PATH 0
#define WALL 1
#define VISITED 2
#define FINAL 3
#define EDGE 4

int maze[MAX+2][MAX+2]={
    {4,4,4,4,4,4,4,4,4,4},
    {4,0,0,0,0,0,0,0,1,4},
    {4,0,1,1,0,1,1,0,1,4},
    {4,0,0,0,1,0,0,0,1,4},
    {4,0,1,0,0,1,1,0,0,4},
    {4,0,1,1,1,0,0,1,1,4},
    {4,0,1,0,0,0,1,0,1,4},
    {4,0,0,0,1,0,0,0,1,4},
    {4,0,1,1,1,0,1,0,0,4},
    {4,4,4,4,4,4,4,4,4,4}
};
int parent[100];
int end, start;

void print_maze(int x, int y);
typedef struct node{
    int dest;       //๋ชฉ์ ๋…ธ๋“œ
    int weight;     //๊ฐ€์ค‘์น˜
    struct node * next;
} Node;

typedef struct list{
    Node * head;
}List;

typedef struct graph{
    int V;
    List * array;
}Graph;

Node * new_node(int dest, int weight){
    Node * new = (Node*)malloc(sizeof(Node));
    new->dest=dest;
    new->weight=weight;
    new->next=NULL;
    return new;
}

Graph * create_graph(int V){
    Graph * g = (Graph*)malloc(sizeof(Graph));
    g->V = V;
    g->array = (List*)malloc(V*sizeof(List));
    for(int i=0;i<V;i++){
        g->array[i].head=NULL;
    }
    return g;
}

void add_edge(Graph *g,int src, int dest, int weight){
    Node * new = new_node(dest, weight);
    new->next=g->array[src].head;
    g->array[src].head=new;

    new=new_node(src, weight);
    new->next = g->array[dest].head;
    g->array[dest].head = new;
}

typedef struct hnode{
    int v;
    int dis;
}HNode;

typedef struct heap{
    int size;
    int capacity;
    int *pos;       //decrease key()์— ํ•„์š”ํ•˜๋‹ค.
    HNode **array;
}Heap;

HNode * new_hnode(int v, int dis){
    HNode * new = (HNode*)malloc(sizeof(HNode));
    new->v=v;
    new->dis=dis;
    return new;
}

Heap * create_heap(int capacity){
    Heap * heap = (Heap*)malloc(sizeof(Heap));
    heap->pos=(int*)malloc(capacity*sizeof(int));
    heap->size=0;
    heap->capacity=capacity;
    heap->array=(HNode**)malloc(capacity*sizeof(HNode*));
    return heap;
}


void swap_node(HNode ** a, HNode **b){
    HNode * tmp =*a;
    *a=*b;
    *b=tmp;
}

void heapify(Heap* heap,int i){
    int min,left,right;
    min=i;
    left = i*2+1;
    right = i*2+2;

    if(left < heap->size && (heap->array[left]->dis < heap->array[min]->dis))min=left;
    if(right<heap->size && heap->array[right]->dis<heap->array[min]->dis)min=right;
    if(min!=i){
        HNode * smallest = heap->array[min];
        HNode * inode = heap->array[i];
        heap->pos[smallest->v]=i;
        heap->pos[inode->v]=min;

        swap_node(&heap->array[min], &heap->array[i]);
        heapify(heap,min);
    }
}

int is_empty(Heap * h){
    return h->size==0;
}

HNode * delete(Heap * h){
    if(is_empty(h))return NULL;

    HNode * root = h->array[0];
    HNode * last = h->array[h->size - 1];

    h->array[0]=last;

    h->pos[root->v]=h->size-1;
    h->pos[last->v]=0;

    --h->size;
    heapify(h, 0);

    return root;
}


void decrease_key(Heap * h, int v, int dis){

    // heap array์˜ ์ •์  v์— ๋Œ€ํ•œ index
    int i = h->pos[v];

    h->array[i]->dis = dis; //distance update
    while(i && ( h->array[i]->dis < h->array[(i-1)/2]->dis)){
        h->pos[h->array[i]->v] = (i-1)/2;
        h->pos[h->array[(i-1)/2]->v] = i;
        swap_node(&h->array[i], &h->array[(i-1)/2]);
        i=(i-1)/2;
    }
}

int is_min(Heap * h, int v){
    if(h->pos[v] < h->size) return 1;
    else return 0;
}

void backtracking(int end){
    int i, j, back;
    int m = MAX+2;
    back = end;
    i  = end / m;
    j  = end % m;

    while( parent[back] != -1)
    {
        back = parent[back];

        maze[i][j] = FINAL;

        i  = back / 10;
        j  = back % 10;
    }
    maze[1][1] = FINAL;
}

void print_array(int dis[],int n){
    printf("์ •์ \t\t์‹œ์ž‘๋…ธ๋“œ๋กœ๋ถ€ํ„ฐ๊ฑฐ๋ฆฌ\n");
    int e = 88;
    for(int i=0;i<n;i++){
        if(i==e)printf("๋„์ฐฉ์ง€!!\n");
        printf("%d\t\t\t%d\n",i,dis[i]);
    }

}

void dijkstra(Graph * g,int src){
    int V= g->V;
    int dis[V];

    Heap * heap = create_heap(V);

    for(int i=0;i<V;i++){
        dis[i]=INT_MAX;
        heap->array[i]=new_hnode(i, dis[i]);
        heap->pos[i]=i;
    }

    // ์ถœ๋ฐœ์ ์˜ ๊ฑฐ๋ฆฌ๋ฅผ 0์œผ๋กœ ๋งŒ๋“ฆ
    heap->array[src]=new_hnode(src, dis[src]);
    heap->pos[src]=src;
    dis[src]=0;
    decrease_key(heap,src,dis[src]);

    heap->size=V;

    while(!is_empty(heap)){
        HNode * min = delete(heap);
        int u = min->v;

        Node * trav = g->array[u].head;
        while(trav!=NULL){
            int v = trav->dest;

            if(is_min(heap, v)&&dis[u]!=INT_MAX && trav->weight+dis[u]<dis[v]){
                dis[v] = dis[u] + trav->weight;
                parent[v]=u;
                maze[u/(MAX+2)][u%(MAX+2)]=VISITED;
                print_maze(u/(MAX+2), u%(MAX+2));
                decrease_key(heap,v,dis[v]);
            }
            trav=trav->next;
        }
    }
    print_array(dis, V);
}
void print_maze(int x,int y){
    // sleep(1);
    // clear();

    for(int i=0;i<MAX+2;i++){
        for(int j=0;j<MAX+2;j++){
            switch (maze[i][j]) {
                case 0:
                    printf(BLACK);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }

                    printf("[]");
                    printf(RESET);
                    break;
                case 1:
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("[]");
                    break;
                case 3:
                    printf(BOLDGREEN);
                    printf("[]");
                    printf(RESET);
                    break;

                case 4:
                    printf(BOLDBLUE);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                        printf("[]");
                    }else
                        printf("[]");
                    printf(RESET);
                    break;
                default:
                    printf(BOLDYELLOW);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("[]");
                    printf(RESET);
                    break;

                    break;
            }
            printf(RESET);
            if(j==MAX+1)printf("\n");
        }
    }
    printf(RESET);
}

int main()
{
    // create the graph given in above fugure

    int m = MAX+2, s;
    Graph * graph = create_graph(m*m);

    start = m*1+1;
    end = m*8+8;

    parent[start] = -1;
    for(int i=1;i<m-1;i++){
        for(int j=1;j<m-1;j++){
            s=i*m+j;
            if(maze[i][j]==PATH){
                if(i==1){
                    if(maze[i+1][j]==PATH)add_edge(graph, s, s+m, 1);
                    if(j==1){
                        if(maze[i][j+1]==PATH)add_edge(graph, s, s+1, 1);
                    }else if(j==m-1){
                        if(maze[i][j+1]==PATH)add_edge(graph, s, s-1, 1);
                    }else{
                        if(maze[i][j+1]==PATH)add_edge(graph, s, s-1, 1);
                        if(maze[i][j+1]==PATH)add_edge(graph, s, s+1, 1);
                    }
                }else if(i==m-2){
                    if(maze[i-1][j]==PATH)add_edge(graph, s, s-m, 1);
                    if(j==1){
                        if(maze[i][j+1]==PATH)add_edge(graph, s, s+1, 1);
                    }else if(j==m-1){
                        if(maze[i][j+1]==PATH)add_edge(graph, s, s-1, 1);
                    }else{
                        if(maze[i][j+1]==PATH)add_edge(graph, s, s-1, 1);
                        if(maze[i][j+1]==PATH)add_edge(graph, s, s+1, 1);
                    }
                }else if(j==1){
                    if(maze[i][j+1]==PATH)add_edge(graph, s, s+1, 1);
                    if(i!=1&&i!=m-2){
                        if(maze[i+1][j]==PATH)add_edge(graph, s, s+m, 1);
                        if(maze[i-1][j]==PATH)add_edge(graph, s, s-m, 1);
                    }
                }else if(j==m-2){
                    if(maze[i][j-1]==PATH)add_edge(graph, s, s-1, 1);
                    if(i!=1&&i!=m-2){
                        if(maze[i+1][j]==PATH)add_edge(graph, s, s+m, 1);
                        if(maze[i-1][j]==PATH)add_edge(graph, s, s-m, 1);
                    }
                }else{
                    if(maze[i+1][j]==PATH)add_edge(graph, s, s+m, 1);
                    if(maze[i-1][j]==PATH)add_edge(graph, s, s-m, 1);
                    if(maze[i][j+1]==PATH)add_edge(graph, s, s+1, 1);
                    if(maze[i][j-1]==PATH)add_edge(graph, s, s-1, 1);
                }
            }

        }
    }
    print_maze(start/m, start%m);
    dijkstra(graph, 11);
    backtracking(end);
    print_maze(end/m, end%m);

    return 0;
}

A*

queue

enQueueํ•  ๋•Œ, ์‚ฝ์ž…์ •๋ ฌ์„ ํ•ด์„œ ๊ฐ’์„ ๋„ฃ์–ด์ค€๋‹ค. (๊ฐ€์ค‘์น˜๊ฐ€ ๋‚ฎ์€ ๊ฐ’์„ ๋จผ์ € ๊บผ๋‚ด๊ธฐ ์œ„ํ•ด์„œ!)

typedef struct vertex{
    int x,y;
    int g_x;
}Vertex;

typedef struct node{
    Vertex ver;
    struct node * next;
}QNode;

typedef struct que{
    QNode *front, *rear;
}Queue;
QNode * new_node(Vertex v){
    QNode * new = (QNode *)malloc(sizeof(QNode));
    new->ver.x = v.x;
    new->ver.y = v.y;
    new->ver.g_x = v.g_x;
    new->next=NULL;
    return new;
}

Queue * creat_queue(void){
    Queue * new = (Queue *)malloc(sizeof(Queue));
    new->front = new->rear= NULL;
    return new;
}

Vertex front(Queue *q){
    return q->front->ver;
}

Vertex rear(Queue *q){
    return q->rear->ver;
}

int is_empty(Queue * q){
    return (q->front==NULL && q->rear==NULL);
}


//front ํฌ์ธํ„ฐ๋Š” ์‚ญ์ œ,  rear ํฌ์ธํ„ฐ๋Š” ์‚ฝ์ž…ํ•  ๋•Œ ์‚ฌ์šฉ
void enQueue(Queue * q,Vertex v){
    QNode * new = new_node(v);
    QNode * tq  =q->front;
    Vertex tmp;
    int key;

    if(is_empty(q)){
        q->front = q->rear = new;
        return;
    }

    //์šฐ์„ ์ˆœ์œ„ํ
    // with insertion-sort, begin sorting process.
    while( tq!= NULL){
        key = weight[v.x][v.y];

        if( key < weight[tq->ver.x][tq->ver.y]){
            tmp = tq->ver;
            tq->ver = v;
            v  = tmp;
        }
        tq = tq->next;
    }
    new->ver = v;
    q->rear->next= new;
    q->rear=new;
}


void deQueue(Queue * q){
    if(q->front==NULL){
        return;
    }
    q->front = q->front->next;
    if(q->front==NULL) q->rear=NULL;
}

heuristic

// heuristicํ•จ์ˆ˜๋กœ ๊ฐ€์ค‘์น˜๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ•จ์ˆ˜
// ์—ฌ๊ธฐ์„œ pre๋Š” ์ด์ „์ •์ ์˜ gx๊ฐ’์„ ๋ฐ›์•„์˜จ๋‹ค.
int heuristic(Vertex v, int x,int y, int *pre){
    int res;

    // h(x)ํ•จ์ˆ˜ ์ฆ‰, ์ถœ๊ตฌ์—์„œ ์–ผ๋งˆ๋‚˜ ๊ฑธ๋ฆฌ๋Š”์ง€ ๊ณ„์‚ฐํ•œ๋‹ค.(๋งจํ•˜ํƒ„)
    res = ((abs(end.x-x)+abs(end.y-y))*10);

    *pre = v.g_x;

    // ๋Œ€๊ฐ์„ ์ธ ๊ฒฝ์šฐ
    if(abs(v.x-x)==abs(v.y-y)){
        *pre = *pre +14;
    }else{
        *pre = *pre +10;
    }
    // f(x) = g(x) + h(x)
    return res+(*pre);
}

open list

// ์ธ์ ‘๋…ธ๋“œ๋ฅผ queue์— ์ถ”๊ฐ€ํ•˜๊ธฐ
void add_openlist(Queue * q,Vertex v){
    Vertex tmp;

    // pw๋Š” ์ด์ „ weigt
    int i,j,w,pre;

    // ์ธ์ ‘ํ•œ ์ •์  ํ™•์ธ
    for(i=v.x-1;i<=v.x+1;i++){

        if(i<1||i>MAX)continue;             // ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜๋ฉด ํ†ต๊ณผํ•œ๋‹ค.
        for(j=v.y-1;j<=v.y+1;j++){
            if(j<1||j>MAX)continue;         // ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜๋ฉด ํ†ต๊ณผํ•œ๋‹ค.
            if(i==v.x&&j==v.y)continue;     // i์™€ j๊ฐ€ ํ˜„์žฌ ๋…ธ๋“œ๋ž‘ ๊ฐ™์œผ๋ฉด ํ†ต๊ณผ
            if(maze[i][j]!=0)continue;      // ๊ธธ์ด ์•„๋‹ˆ๋ฉด ํ†ต๊ณผ

            // ๊ฐ€์ค‘์น˜ f(x)
            w = heuristic(v, i, j, &pre);

            // ๊ฐ€์ค‘์น˜๊ฐ€ ํ˜„์žฌ๋ณด๋‹ค ๋‚ฎ๊ฑฐ๋‚˜ ๊ธฐ๋ก์ด ์•ˆ๋˜์–ด์žˆ์œผ๋ฉด ๊ฐฑ์‹ 
            if(w<weight[i][j]||weight[i][j]==0){
                weight[i][j]=w;
                // ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•œ๋‹ค.
                parent[i][j] = (v.x*MAX+2)+v.y;

                // ์ถœ๊ตฌ๋ฅผ ์ฐพ์œผ๋ฉด ์ข…๋ฃŒ
                if(end.x == i && end.y ==j)return;

            }
            tmp.x = i;
            tmp.y = j;
            tmp.g_x = pre;
            enQueue(q, tmp);
        }
    }

}

astar

void astar(Vertex s,Vertex e){

    Queue * q = creat_queue();

    Vertex v;

    // ์‹œ์ž‘์ ์˜ weight๋Š” 0์ด๋‹ค.
    weight[s.x][s.y] = 0;
    // ์‹œ์ž‘์ ์€ ๋ถ€๋ชจ๋…ธ๋“œ๋ฅผ ๊ฐ–๊ณ  ์žˆ์ง€ ์•Š๋Š”๋‹ค.
    parent[s.x][s.y]=-1;
    // ์‹œ์ž‘์ ์—์„œ ์›€์ง์ธ ๊ฑฐ๋ฆฌ(gx)๋Š” 0์ด๋‹ค.
    s.g_x = 0;

    v = s;

    add_openlist(q,v);

    while(!is_empty(q)){


        // ํ˜„์žฌ ์ ์„ Closed list์— ์ถ”๊ฐ€ >> maze์— ๋ฐ”๋กœํ‘œ์‹œ
        maze[v.x][v.y]=CLOSED;
        v = front(q);
        deQueue(q);
        if(v.x==end.x && v.y==end.y)return;

        // ์ƒˆ๋กœ์šด ์ธ์ ‘๋…ธ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•ด์ค€๋‹ค.
        add_openlist(q, v);

    }   
}

backtracking

void backtracking(){
    int i, j, back;

    if(parent[end.x][end.y]==0){
        printf("๊ฒฝ๋กœ๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.\n");
        return;
    }

    i  = parent[end.x][end.y] / MAX+2;
    j  = parent[end.x][end.y] % MAX+2;

    while( parent[i][j] != -1)
    {
        back = parent[i][j];

        maze[i][j] = FINAL;

        i  = back / MAX+2;
        j  = back % MAX+2;
    }
    maze[start.x][start.y] = FINAL;
}

print

void print_weight(){
    int i,j;
    for(i=0;i<MAX+2;i++){
        for(j=0;j<MAX+2;j++)
            printf("%6d",weight[i][j]);
        printf("\n");
    }

}
void print_maze(int x,int y){
    for(int i=0;i<MAX+2;i++){
        for(int j=0;j<MAX+2;j++){
            switch (maze[i][j]) {
                case 0:
                    printf(BLACK);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }

                    printf("[]");
                    printf(RESET);
                    break;
                case 1:
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("[]");
                    break;
                case 3:
                    printf(BOLDGREEN);
                    printf("[]");
                    printf(RESET);
                    break;

                case 4:
                    printf(BOLDBLUE);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                        printf("[]");
                    }else
                        printf("[]");
                    printf(RESET);
                    break;
                default:
                    printf(BOLDYELLOW);
                    if(i==x&&j==y){
                        printf(BOLDRED);
                    }
                    printf("[]");
                    printf(RESET);
                    break;

                    break;
            }
            printf(RESET);
            if(j==MAX+1)printf("\n");
        }
    }
    printf(RESET);
}

main

int main(){
    start.x=1;start.y=1;
    end.x=MAX;end.y=MAX;
    astar(start, end);
    print_weight();
    print_maze(end.x,end.y);
    backtracking();
    print_maze(end.x,end.y);
}
PreviousTreeNextAVL

Last updated 4 years ago

Was this helpful?

์— ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด์„œ ์ž์„ธํžˆ ์„ค๋ช…๋˜์–ด์žˆ๋‹ค.

A* ์•Œ๊ณ ๋ฆฌ์ฆ˜